What is protected division? (in reference to genetic programming and cryptography)

Question

I am getting references in a paper on genetic programming, to a "protected division" operation. When I google this, i get mostly papers on genetic programming and various results related to cryptography, but none that explain what it actually is. Does anybody know?

Erle

Answer 1

Protected division (often notated with %) checks to see if its second argument is 0. If so, % typically returns the value 1 (regardless of the value of the first argument).

http://en.wikipedia.org/wiki/Genetic_programming

In cryptography it doesn't seem to be well-defined, but the top google hit is for protecting against side channel attacks (in that case, via power use - you can guess what numbers are being used in the division by looking at the power consumption of the hardware doing the encryption) http://dl.acm.org/citation.cfm?id=1250996 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.7298&rep=rep1&type=pdf

Fantastically

well thats quite simple. Wish I understood the link. Thank you very much! – Erle

Answer 2

In GP protected division is a modified division operator which does not signal "division by zero" error when denominator is 0 (zero). It typically returns 1 when denominator is zero.

Belter

Optionally the protected division also influences the fitness of the program such that (almost) causing a "division by zero" error is punished. – Anzio

Answer 3

It divides on threshold function of argument instead of argument.

Thres(x) = epsilon*Theta(x) if fabs(x)<epsilon.

Where Theta() is non-zero variant of theta-function.

Other threshold functions possible. Or sometimes it is just 'epsilon'.

Multivibrator

Answer 4

When evolving programs with Genetic Programming (GP), every generated program is tested to get its fitness value. The protected division is required when the evolved programs are mathematical expressions. In cryptography, the mathematical expression might be used to model a decision-making process. In the evaluation step, the program may perform a division by zero, which would cause a crash. To avoid this, the protected division is set to return a specific value if the denominator equals zero. I've seen three settings:

• If the denominator equals zero, return 1
• If the denominator equals zero, return 0
• If the denominator equals zero, return the numerator

The setting should be specified somewhere in the paper. If not, the safest bet is to assume that the protected division returns the numerator. Given that 1 is a multiplicative neutral and 0 is an additive neutral, they could cause some bias in the programs generated during the evolution but are still commonly used.

Hiram

Answer 5

The above answers are good, but my advice is to avoid protected division because the results are unpredictable.

Rather, if you get division by zero (or any other exception) do modify (mutate) that operator into another one which does not generate an exception.

I did implemented this strategy into Multi Expression Programming.

Here is a code snippet relevant to this case:

void compute_eval_matrix(const t_mep_chromosome &c, int code_length, int num_variables,
int num_training_data,  const double **training_data, 
double **eval_matrix)
{
for (int i = 0; i < code_length; i++){   // read the chromosome from top to down
    bool is_error_case = false;// division by zero, other errors
    switch (c.code[i].op) {

    case  DIV_OP:  //  handle division
        for (int k = 0; k < num_training_data; k++)
            if (fabs(eval_matrix[c.code[i].addr2][k]) < 1e-6) // test if it is too small
                is_error_case = true;
        if (is_error_case) {                                           // an division by zero error occured !!!
            c.code[i].op = rand() % num_variables;   // the gene is mutated into a terminal
            for (int k = 0; k < num_training_data; k++)
                eval_matrix[i][k] = training_data[k][c.code[i].op];
        }
        else    // normal execution....
            for (int k = 0; k < num_training_data; k++)
                eval_matrix[i][k] = eval_matrix[c.code[i].addr1][k] / eval_matrix[c.code[i].addr2][k];
        break;
    default:  // a variable
        break;
    } // end switch
} // end for
}

Deception