secure_svm.cpp

Go to the documentation of this file.

/*
SeComLib
Copyright 2012-2013 TU Delft, Information Security & Privacy Lab (http://isplab.tudelft.nl/)

Contributors:
Inald Lagendijk (R.L.Lagendijk@TUDelft.nl)
Mihai Todor (todormihai@gmail.com)
Thijs Veugen (P.J.M.Veugen@tudelft.nl)
Zekeriya Erkin (z.erkin@tudelft.nl)

Licensed 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.
*/
#include "secure_svm.h"
//avoid circular includes
#include "server.h"

namespace SeComLib {
namespace SecureRecommendations {
    const SecureSvm::EncryptedVector SecureSvm::nullVector;

    const std::map<std::string, SecureSvm::KernelTypes> SecureSvm::kernelTypesMap = boost::assign::map_list_of("linear", SecureSvm::linear)
                                                                                                                ("homogeneous_poly", SecureSvm::homogeneousPolynomial)
                                                                                                                ("inhomogeneous_poly", SecureSvm::inhomogeneousPolynomial)
                                                                                                                ("rbf", SecureSvm::inverseQuadraticRBF);

    SecureSvm::SecureSvm (const std::string &directoryPath, const std::string &modelFile, const PaillierPublicKey &publicKey, const std::weak_ptr<const Server> &server) : cryptoProvider(publicKey), server(server), modelFileName(modelFile), model(NULL) {
        //set configuration parameters
        this->featureScalingFactor = BigInteger(10).Pow(Utils::Config::GetInstance().GetParameter<unsigned long>("SecureRecommendations.Svm.minimumFeatureDecimalDigits"));
        this->minimumAiDecimalDigits = Utils::Config::GetInstance().GetParameter<unsigned short>("SecureRecommendations.Svm.minimumAiDecimalDigits");

        //set the kernel
        this->kernel = SecureSvm::GetKernel(Utils::Config::GetInstance().GetParameter<std::string>("SecureRecommendations.kernel"));

        //set the safety block models specific parameters
        this->safetyModelFilePrefix = Utils::Config::GetInstance().GetParameter<std::string>("SecureRecommendations.Server.SafetyBlock.modelFilePrefix");

        //parse the unsafe classes for the safety models
        if (std::string::npos != this->modelFileName.find(this->safetyModelFilePrefix)) {
            std::vector<unsigned short> unsafeClasses;
            //iterate over each class (digit) in the file name
            for (size_t i = this->safetyModelFilePrefix.size(); i <  this->modelFileName.find("."); ++i) {
                //the difference between any digit and '0' will yield the desired numeric value
                unsafeClasses.emplace_back(this->modelFileName[i] - '0');
            }

            std::sort(unsafeClasses.begin(), unsafeClasses.end());

            //convert the ordered unsafeClasses vector to a stringstream
            std::stringstream unsafeClassesStream;
            for (std::vector<unsigned short>::const_iterator unsafeClassesIterator = unsafeClasses.begin(); unsafeClassesIterator != unsafeClasses.end(); ++unsafeClassesIterator) {
                unsafeClassesStream << *unsafeClassesIterator;
            }
            this->safetyModelUnsafeClasses = unsafeClassesStream.str();
        }

        //get the inverse quadratic RBF kernel configuration parameters
        if (SecureSvm::inverseQuadraticRBF == this->kernel) {
            this->inverseQuadraticRbfKernelRelevantDigits = Utils::Config::GetInstance().GetParameter<unsigned short>("SecureRecommendations.Svm.inverseQuadraticRbfKernelRelevantDigits");

            unsigned long blindingFactorSize = Utils::Config::GetInstance().GetParameter<unsigned long>("SecureRecommendations.Server.blindingFactorSize");
            this->blindingFactorScaling = BigInteger(2).Pow(blindingFactorSize + 1);//the maximum value of the blinding may have blindingFactorSize + 1 bits
        }

        std::string modelFilePath = directoryPath + this->modelFileName;

        std::ifstream fileStream(modelFilePath);

        //test if the file exists and can be accessed
        if (!fileStream.good()) {
            throw std::runtime_error("Can't open the SVM model file.");
        }

        if (SecureSvm::linear != this->kernel) {
            //we must read the gamma parameter from the file as a string, to determine the scaling that needs to be applied to it, such that it ends up being > 0 and we don't loose precision
            std::string line;
            bool foundGamma = false;
            while (std::getline(fileStream, line)) {
                if (std::string::npos != line.find("gamma")) {
                    //we only scale gamma if it has a radix point
                    if (std::string::npos != line.find('.')) {
                        std::string gammaValueString = line.substr(line.find(' '));
                        std::stringstream gammaValueStream; gammaValueStream << gammaValueString;
                        double gammaValue; gammaValueStream >> gammaValue;

                        //if gamma has decimals, then it *must* be a negative power of 2...
                        double exponent = std::log(gammaValue) / std::log(2.0);
                        if (exponent > 0) throw std::runtime_error("Unexpected gamma value detected.");
                        
                        //we want to compute the scaling such that gamma * scaling = 1
                        //first, we round the negative number towards the closest integer
                        this->gammaScaling = BigInteger(2).Pow(static_cast<unsigned long>(std::abs(std::ceil(exponent - 0.5))));
                    }
                    else {
                        //gamma is already an integer
                        this->gammaScaling = 1;
                    }

                    foundGamma = true;
                    break;
                }
            }
            //sanity check
            if (!foundGamma)
                throw std::runtime_error("Can't find gamma in the model file.");
        }

        //close the file stream
        fileStream.close();

        //use the libsvm library to parse the model file
        this->model = svm_load_model(modelFilePath.c_str());

        if (NULL == this->model) {
            throw std::runtime_error("Invalid model file.");
        }

        this->preprocessData();

        std::cout << "Loaded " << modelFile << "; nSV: " << this->model->l << std::endl;
    }

    SecureSvm::~SecureSvm () {
        svm_free_and_destroy_model(&this->model);
    }

    SecureSvm::KernelTypes SecureSvm::GetKernel (const std::string &input) {
        std::map<std::string, KernelTypes>::const_iterator iterator = SecureSvm::kernelTypesMap.find(input);

        //if the specified kernel name is not found
        if (SecureSvm::kernelTypesMap.end() == iterator) {
            throw std::runtime_error("Invalid kernel name received.");
        }

        return iterator->second;
    }

    const std::string &SecureSvm::GetUnsafeClasses () const {
        return this->safetyModelUnsafeClasses;
    }

    Paillier::Ciphertext SecureSvm::Predict (const SecureSvm::EncryptedVector &x, const SecureSvm::EncryptedVector &xx, const SecureSvm::EncryptedVector &xSquared) const {
        Paillier::Ciphertext output = this->encryptedZero;

        //stores the values for the inverse quadratic RBF kernel
        SecureSvm::EncryptedVector inverseQuadraticRbfKernelValues;

        //iterate over the model rows (vectors)
        for (size_t i = 0; i < this->aVector.size(); ++i) {
            Paillier::Ciphertext encryptedKernelValue;

            //compute kernel
            switch (this->kernel) {
                case SecureSvm::linear:
                    encryptedKernelValue = this->linearKernel(x, this->sMatrix[i]);
                    break;
                case SecureSvm::homogeneousPolynomial:
                    encryptedKernelValue = this->homogeneousPolynomialKernel(xx, this->twoGammaSquaredSSMatrix[i]);
                    break;
                case SecureSvm::inhomogeneousPolynomial:
                    encryptedKernelValue = this->inhomogeneousPolynomialKernel(x, xx, this->twoGammaSMatrix[i], this->twoGammaSquaredSSMatrix[i]);
                    break;
                case SecureSvm::inverseQuadraticRBF:
                    inverseQuadraticRbfKernelValues.emplace_back(this->computeInverseQuadraticRbfKernelDenominator(x, xSquared, this->minusTwoSMatrix[i], encryptedSSquaredMatrix[i]));
                    break;
                default:
                    throw std::runtime_error("Invalid kernel type.");
            }
            

            //compute this separately for the inverse quadratic RBF kernel
            if (SecureSvm::inverseQuadraticRBF != this->kernel) {
                output = output + encryptedKernelValue * this->aVector[i];
            }
        }

        if (SecureSvm::inverseQuadraticRBF == this->kernel) {

            //debug
            //std::cout << "numerator:" << this->inverseQuadraticRbfNumerator.ToString(10) << std::endl;

            //replace the denominator values with the actual kernel values
            this->server.lock()->InteractiveSecureDivision(this->inverseQuadraticRbfNumerator, inverseQuadraticRbfKernelValues);

            for (size_t i = 0; i < this->aVector.size(); ++i) {
                //debug
                //this->server.lock()->DebugValue(inverseQuadraticRbfKernelValues[i]);
                //std::cout << this->aVector[i].ToString(10).c_str() << std::endl;

                output = output + inverseQuadraticRbfKernelValues[i] * this->aVector[i];

                //debug
                //this->server.lock()->DebugValue(this->cryptoProvider.HomomorphicMultiply(inverseQuadraticRbfKernelValues[i], this->aVector[i]));
                //this->server.lock()->DebugValue(output);
            }

            //debug
            //this->server.lock()->DebugValue(output);
            //this->server.lock()->DebugValue(this->encryptedB);
        }

        output = output + this->encryptedB;

        //debug
        //this->server.lock()->DebugValue(output);

        return output;
    }

    void SecureSvm::preprocessData () {
        if (this->model->label[0] < 0)
            this->reversedSign = true;
        else
            this->reversedSign = false;

        //model->param.gamma is unitialized in the case of the linear kernel and it's not used in the formula
        if (SecureSvm::linear != this->kernel) {
            this->scaledGamma = BigInteger(this->model->param.gamma, this->gammaScaling);
            
            //debug
            //std::cout << this->scaledGamma.ToString(10).c_str() << std::endl;
            //std::cout << this->gammaScaling.ToString(10).c_str() << std::endl;
        }

        this->svWeightScaling = BigInteger(10).Pow(static_cast<unsigned long>(this->minimumAiDecimalDigits));

        //std::cout << this->svWeightScaling.ToString(10).c_str() << std::endl;

        double minAbsAi = std::abs(this->model->sv_coef[0][0]);
        for (unsigned int i = 1; i < static_cast<unsigned int>(this->model->l); ++i) {
            if (minAbsAi > std::abs(this->model->sv_coef[0][i])) {
                minAbsAi = std::abs(this->model->sv_coef[0][i]);
            }
        }
        //compute the minimum between min(a_i) and b
        double minAbsAiB = minAbsAi;
        if (minAbsAi > std::abs(this->model->rho[0])) {
            minAbsAiB = std::abs(this->model->rho[0]);
        }

        //debug
        //std::cout << minAbsAiB << std::endl;

        //iterate over the model rows (vectors)
        for (unsigned int i = 0; i < static_cast<unsigned int>(this->model->l); ++i) {
            //double aValue = this->reversedSign ? -this->model->sv_coef[0][i]: this->model->sv_coef[0][i];
            double aValue = this->reversedSign ? -this->model->sv_coef[0][i] / minAbsAiB : this->model->sv_coef[0][i] / minAbsAiB;
            this->aVector.emplace_back(BigInteger(aValue, this->svWeightScaling));

            //debug
            /*
            if (this->aVector.back() > this->cryptoProvider.GetMessageSpaceUpperBound() / 2) {
                std::cout << "-" << (this->cryptoProvider.GetMessageSpaceUpperBound() - this->aVector.back()).ToString(10).c_str() << std::endl;
            }
            else
                std::cout << this->aVector.back().ToString(10).c_str() << std::endl;
            */
        }

        
        //construct the scaling for b (see the description of each kernel for the detailed formulas)
        BigInteger bScaling(this->svWeightScaling);//apply the SVM parameter scaling (to compensate for the scaling applied to a_i)
        
        //compensate for scalings applied to s_i and x_i
        switch (this->kernel) {
            case SecureSvm::linear:
                //compensate for s_i * x_i
                bScaling *= this->featureScalingFactor;
                bScaling *= this->featureScalingFactor;
                break;
            case SecureSvm::homogeneousPolynomial:
            case SecureSvm::inhomogeneousPolynomial:
                //compensate for (gamma s_i * x_i)^2 or (gamma s_i * x_i + 1)^2
                bScaling *= this->gammaScaling;
                bScaling *= this->gammaScaling;
                bScaling *= this->featureScalingFactor;
                bScaling *= this->featureScalingFactor;
                bScaling *= this->featureScalingFactor;
                bScaling *= this->featureScalingFactor;
                break;
            case SecureSvm::inverseQuadraticRBF:
                //compensate for the digits preserved from the kernel value
                bScaling *= BigInteger(10).Pow(static_cast<unsigned long>(this->inverseQuadraticRbfKernelRelevantDigits));
                //compensate for the secure division blinding factor
                bScaling *= this->blindingFactorScaling;
                break;
            default:
                throw std::runtime_error("Invalid kernel type.");
        }

        //remap negative values to the upper part of the crypto provider message space
        //libsvm negates rho before adding it to the sum. We also need to check if the sign of the prediction needs to be inverted
        //double bValue = this->reversedSign ? this->model->rho[0] : -(this->model->rho[0]);
        double bValue = this->reversedSign ? this->model->rho[0] / minAbsAiB : -(this->model->rho[0] / minAbsAiB);
        BigInteger scaledB = BigInteger(bValue, bScaling);
        
        //encrypt scaled b
        this->encryptedB = this->cryptoProvider.EncryptInteger(scaledB);

        //debug
        //std::cout this->svWeightScaling.ToString(10).c_str() << std::endl;
        //this->server.lock()->DebugValue(this->encryptedB);
        
        BigInteger two(2);
        BigInteger gammaSquared = this->scaledGamma.GetPow(2);
        //iterate over the model rows (vectors)
        for (unsigned int row = 0; row < static_cast<unsigned int>(this->model->l); ++row) {
            SecureSvm::ModelVector tempS;

            SecureSvm::ModelVector tempTwoGammaS;

            SecureSvm::ModelVector tempMinusTwoS;

            SecureSvm::ModelVector tempTwoGammaSquaredSS;

            SecureSvm::EncryptedVector tempEncryptedSSquared;

            //create an iterator for the model row (vector)
            svm_node *iterator = this->model->SV[row];

            //collect all the weights for the current row (vector)
            //libsvm implementation detail: iterator->index is set to -1 after the last attribute weight in the vector
            //we assume that no attribute weights are omitted in the model file (the format specifies that 0 valued weights can be omitted)
            while (-1 != iterator->index) {
                //scale the current value and load it in a buffer variable
                BigInteger tempSValue(iterator->value, this->featureScalingFactor);

                //we need to have values greater than 0 in order to ensure security
                if (tempSValue == 0) {
                    tempSValue = 1;
                }

                //debug
                //std::cout << tempSValue.ToString(10) << std::endl;

                tempS.push_back(tempSValue);

                ++iterator;
            }

            //s matrix is needed only for the linear kernel
            if (SecureSvm::linear == this->kernel) {
                //populate the s matrix
                this->sMatrix.emplace_back(tempS);
            }

            //compute auxiliary matrices for the polynomial and RBF kernels
            if (SecureSvm::linear != this->kernel) {
                for (size_t i = 0; i < tempS.size(); ++i) {
                    //twoGammaSquaredSS matrix is not required for the inverse quadratic RBF kernel
                    if (SecureSvm::inverseQuadraticRBF != this->kernel) {
                        for (size_t j = i; j < tempS.size(); ++j) {
                            if (i != j) {
                                tempTwoGammaSquaredSS.push_back(two * gammaSquared * tempS[i] * tempS[j]);
                            }
                            else {
                                tempTwoGammaSquaredSS.push_back(gammaSquared * tempS[i] * tempS[j]);
                            }
                        }
                    }

                    if (SecureSvm::inhomogeneousPolynomial == this->kernel) {
                        //get local copy of the current scaled value
                        BigInteger tempSValue = tempS[i];

                        //need to compensate for gamma^2 * x^2 * s^2
                        //we already have gammaScaling * featureScalingFactor, so we add the rest
                        tempSValue *= this->gammaScaling;
                        tempSValue *= this->featureScalingFactor;
                        tempSValue *= this->featureScalingFactor;
                        tempTwoGammaS.push_back(two * this->scaledGamma * tempSValue);
                    }

                    //encrypted sSquared and minusTwoS matrices are required only for the inverse quadratic RBF kernel
                    if (SecureSvm::inverseQuadraticRBF == this->kernel) {
                        tempEncryptedSSquared.push_back(this->cryptoProvider.EncryptInteger(tempS[i].GetPow(2)));

                        tempMinusTwoS.push_back(-two * tempS[i]);//use unary - operator
                    }
                }

                //twoGammaSquaredSS matrix is not requred for the inverse quadratic RBF kernel
                if (SecureSvm::inverseQuadraticRBF != this->kernel) {
                    this->twoGammaSquaredSSMatrix.emplace_back(tempTwoGammaSquaredSS);
                }

                //twoGammaS matrix is required for the inhomogeneous polynomial kernel
                if (SecureSvm::inhomogeneousPolynomial == this->kernel) {
                    this->twoGammaSMatrix.emplace_back(tempTwoGammaS);
                }

                //minusTwoS and encryptedSSquared matrices are required for the inverse quadratic RBF kernel
                if (SecureSvm::inverseQuadraticRBF == this->kernel) {
                    this->minusTwoSMatrix.emplace_back(tempMinusTwoS);

                    this->encryptedSSquaredMatrix.emplace_back(tempEncryptedSSquared);
                }
            }
        }//model rows

        if (SecureSvm::inhomogeneousPolynomial == this->kernel) {
            BigInteger one(1);
            //need to compensate for gamma^2 * x^2 * s^2
            one *= this->gammaScaling;
            one *= this->gammaScaling;
            one *= this->featureScalingFactor;
            one *= this->featureScalingFactor;
            one *= this->featureScalingFactor;
            one *= this->featureScalingFactor;
            this->encryptedScaledOne = this->cryptoProvider.EncryptInteger(one);
        }

        
        if (SecureSvm::inverseQuadraticRBF == this->kernel) {
            BigInteger one(1);
            //need to compensate for gamma * (x - s)^2
            one *= this->gammaScaling;
            one *= this->featureScalingFactor;
            one *= this->featureScalingFactor;
            this->encryptedScaledOne = this->cryptoProvider.EncryptInteger(one);

            this->inverseQuadraticRbfNumerator = BigInteger(1);
            //compensate for the random blinding
            this->inverseQuadraticRbfNumerator *= this->blindingFactorScaling;
            //compensate for gamma * (x - s)^2
            this->inverseQuadraticRbfNumerator *= this->gammaScaling;
            this->inverseQuadraticRbfNumerator *= this->featureScalingFactor;
            this->inverseQuadraticRbfNumerator *= this->featureScalingFactor;
            //preserve the required number of digits after performing division
            this->inverseQuadraticRbfNumerator *= BigInteger(10).Pow(static_cast<unsigned long>(inverseQuadraticRbfKernelRelevantDigits));
        }

        this->encryptedZero = this->cryptoProvider.GetEncryptedZero();
    }

    Paillier::Ciphertext SecureSvm::linearKernel (const SecureSvm::EncryptedVector &x, const SecureSvm::ModelVector &s) const {
        Paillier::Ciphertext output = this->encryptedZero;

        for (size_t i = 0; i < s.size(); ++i) {
            //debug
            /*
            this->server.lock()->DebugValue(x[i]);
            std::cout << s[i].ToString(10) << std::endl;
            */
            output = output + x[i] * s[i];
        }
        
        return output;
    }

    Paillier::Ciphertext SecureSvm::homogeneousPolynomialKernel (const SecureSvm::EncryptedVector &xx, const SecureSvm::ModelVector &twoGammaSquaredSS) const {
        Paillier::Ciphertext output = this->encryptedZero;

        for (size_t i = 0; i < xx.size(); ++i) {
            output = output + xx[i] * twoGammaSquaredSS[i];
        }
    
    #if 0
        /* previous algorithm with complex index logic. Now, we just do sum(2*(xi xj)(si sj)) if i != j and sum((xi xj)(si sj)) if i==j in the encrypted domain */

        for (size_t i = 0; i < s.size(); ++i) {
            for (size_t j = 0; j < s.size(); ++j) {
                //the x_ix_j matrix is unraveled into a vector, xx, so we need to compute the apropriate index
                //basically, we need to subtract sum(i - 1) = (i - 1) * i / 2 at each step to determine the index in the vector
                size_t index;
                if (i <= j) {
                    //the upper triangle of the x_ix_j matrix
                    index = i * (s.size() - 1) - (i - 1) * i / 2 + j;
                }
                else {
                    //the lower triangle of the x_ix_j matrix is symmetric to the upper one, so we remap it there
                    index = j * (s.size() - 1) - (j - 1) * j / 2 + i;
                    
                }

                //std::cout << "i: " << i << "; j: " << j << "; index: " << index << std::endl;

                output = output + xx[index] * ss[index];
            }
        }
    #endif
        
        return output;
    }

    Paillier::Ciphertext SecureSvm::inhomogeneousPolynomialKernel (const SecureSvm::EncryptedVector &x, const SecureSvm::EncryptedVector &xx, const SecureSvm::ModelVector &twoGammaS, const SecureSvm::ModelVector &twoGammaSquaredSS) const {
        //leverage the homogeneousPolynomialKernel and linearKernel implementations to simplify the formula
        return this->homogeneousPolynomialKernel(xx, twoGammaSquaredSS) + this->linearKernel(x, twoGammaS) + this->encryptedScaledOne;
    }

    Paillier::Ciphertext SecureSvm::computeInverseQuadraticRbfKernelDenominator (const SecureSvm::EncryptedVector &x, const SecureSvm::EncryptedVector &xSquared, const SecureSvm::ModelVector &minusTwoS, const SecureSvm::EncryptedVector &encryptedSSquared) const {
        Paillier::Ciphertext encryptedDenominator = this->encryptedZero;

        for (size_t i = 0; i < x.size(); ++i) {
            encryptedDenominator = encryptedDenominator + xSquared[i] + x[i] * minusTwoS[i] + encryptedSSquared[i];

        }

        //multiply (d, gamma), since gamma is the unencrypted value...
        encryptedDenominator = this->encryptedScaledOne + encryptedDenominator * this->scaledGamma;

        return encryptedDenominator;
    }

}//namespace SecureRecommendations
}//namespace SeComLib