• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

[Report] How I caught a cheater

campos20

Member
Joined
Dec 26, 2015
Messages
36
Location
Brazil, MG
WCA
2015CAMP17
YouTube
Visit Channel
Are you familiar with online judge system for programming?
Some examples: SPOJ, Codechef, UVA, URI.

This report is about SPOJ. One thing that I like about SPOJ is that if you fill some requirements, you can create your own Problems for others to solve and a custom judge (which is optional for a problem).

That said (written), I created a Problem in which the user has a set of scrambled Rubik's cube to solve (using any programming language), called God Number is 20. Originally, there was 51 fixed cubes to be solved, pre-generated (in my computer) using 50 random moves each. Also, I created a custom judge to check that any valid solution generated by the user would be accepted (I put a lot of effort on it, since I run into programming problems, cubing problems, SPOJ problems...).

The problem ranks the competitors based on the number of moves for the entire set of cubes. So, fewer moves is better. A user got a score of 1034 (which means 1034/51 = 20,3 moves/cube).

Now the cheating comes.
The input (random cubes) was not meant to be known by any user (user can't even have access to s/his own output), but a user guessed the input. How? Well, it was clever and painstaking. Since the set of cubes was fixed, every time a program was sent, the cube position (stickers) would be in the same place. I started suspecting when two solutions scored 889 (889/51 = 17,4 moves/cube), perfect score.

full


Since I am the problem setter, I have access to the source code. Taking a look at it, the first statement was:

Code:
/** This is Stefan Pochmann's public code and all the credit goes to him. We thank him for this beautiful implementation. **/

A decided to find Pochmann in Facebook. He was kind (and helpful) enough to state that he did have a program written for a contest, but it would not produce the perfect score. He came up with this crazy idea for guessing the input:

Suppose you have a solution (any method) for the problem where you get a score of 2000. Then, you change the program (to be submitted again) to do the following:
*if the first sticker is Green, you add U2 U2 (The cube is still solved, and you can observe your score change to 2002)
*if the first sticker is Yellow, you add U2 U2 U2 U2 (score will be 2004).
*if the first sticker is White, add (U2 U2 U2 U2 U2 U2 score will be 2006).
*etc

In this way, one can guess the sticker by observing how the score changed. Actually, a program can guess more than 1 sticker at a time. Since there was 51 cubes, the cheater would have to guess at most 51*54 = 2754 stickers.

I was surprised when I observed that other solutions, with ridiculous high scores (remember, high is bad) produced a lot of F2 F2..., just like Pochmann predicted.

full


Don't get me wrong. I have a big respect for this user who put effort on this, but this was not what the contest was meant for. I decided to change the judge. Currently, it generates 51 random cubes, using 30 random moves each (actually, 1 cube uses 2 moves) and all the submissions were rejudge in this new judge. There's no way to guess input now, since it changes for each submission. After the submission, the user can have access to the random moves produced by the judge.

This is the first version of the Judge (which used the fixed set of cubes)

Code:
/*
    Author: Alexandre Henrique Afonso Campos
    Judge for: www.spoj.com/problems/GODNIS20/
    Created: 13 Fev 2016
    Finished: 27 Fev 2016
    Thanks: Mitch Schwartz
*/

#include "spoj.h"
#include <stdio.h>
#include <string.h>

#define ReadColor(i, j, k) { color = read_color(); if (color == -1) return -1; cube[(i)][(j)][(k)] = color; }

//FILE* spoj_p_in;
//FILE* spoj_t_out;

// U -> 0
// L -> 1
// F -> 2
// R -> 3
// B -> 4
// D -> 5

// targets of the moves
int    U_perm[5][4][3] = { { {1, 0, 0}, {4, 0, 0}, {3, 0, 0}, {2, 0, 0} }, { {1, 0, 1}, {4, 0, 1}, {3, 0, 1}, {2, 0, 1} }, { {1, 0, 2}, {4, 0, 2}, {3, 0, 2}, {2, 0, 2} }, {{0, 0, 0}, {0, 0, 2}, {0, 2, 2}, {0, 2, 0}}, {{0, 0, 1}, {0, 1, 2}, {0, 2, 1}, {0, 1, 0}} },
    L_perm[5][4][3] = { { {0, 0, 0}, {2, 0, 0}, {5, 0, 0}, {4, 2, 2} }, { {0, 1, 0}, {2, 1, 0}, {5, 1, 0}, {4, 1, 2} }, { {0, 2, 0}, {2, 2, 0}, {5, 2, 0}, {4, 0, 2} }, {{1, 0, 0}, {1, 0, 2}, {1, 2, 2}, {1, 2, 0}}, {{1, 0, 1}, {1, 1, 2}, {1, 2, 1}, {1, 1, 0}} },
    F_perm[5][4][3] = { { {0, 2, 0}, {3, 0, 0}, {5, 0, 2}, {1, 2, 2} }, { {0, 2, 1}, {3, 1, 0}, {5, 0, 1}, {1, 1, 2} }, { {0, 2, 2}, {3, 2, 0}, {5, 0, 0}, {1, 0, 2} }, {{2, 0, 0}, {2, 0, 2}, {2, 2, 2}, {2, 2, 0}}, {{2, 0, 1}, {2, 1, 2}, {2, 2, 1}, {2, 1, 0}} },
    R_perm[5][4][3] = { { {0, 2, 2}, {4, 0, 0}, {5, 2, 2}, {2, 2, 2} }, { {0, 1, 2}, {4, 1, 0}, {5, 1, 2}, {2, 1, 2} }, { {0, 0, 2}, {4, 2, 0}, {5, 0, 2}, {2, 0, 2} }, {{3, 0, 0}, {3, 0, 2}, {3, 2, 2}, {3, 2, 0}}, {{3, 0, 1}, {3, 1, 2}, {3, 2, 1}, {3, 1, 0}} },
    B_perm[5][4][3] = { { {0, 0, 2}, {1, 0, 0}, {5, 2, 0}, {3, 2, 2} }, { {0, 0, 1}, {1, 1, 0}, {5, 2, 1}, {3, 1, 2} }, { {0, 0, 0}, {1, 2, 0}, {5, 2, 2}, {3, 0, 2} }, {{4, 0, 0}, {4, 0, 2}, {4, 2, 2}, {4, 2, 0}}, {{4, 0, 1}, {4, 1, 2}, {4, 2, 1}, {4, 1, 0}} },
    D_perm[5][4][3] = { { {2, 2, 0}, {3, 2, 0}, {4, 2, 0}, {1, 2, 0} }, { {2, 2, 1}, {3, 2, 1}, {4, 2, 1}, {1, 2, 1} }, { {2, 2, 2}, {3, 2, 2}, {4, 2, 2}, {1, 2, 2} }, {{5, 0, 0}, {5, 0, 2}, {5, 2, 2}, {5, 2, 0}}, {{5, 0, 1}, {5, 1, 2}, {5, 2, 1}, {5, 1, 0}} };

int cube[6][3][3];

// BEGIN MOVE THE CUBE
void move_perm(int perm[5][4][3], int d) {
    int i, j;
   
    for (i=0; i<5; i++){
        int temp[4];
       
        for (j=0; j<4; j++) {
            temp[j] = cube[perm[i][j][0]][perm[i][j][1]][perm[i][j][2]];
        }
       
        for (j=0; j<4; j++) {
            cube[perm[i][j][0]][perm[i][j][1]][perm[i][j][2]] = temp[(4+j-d)%4];
        }
    }
}

void move_face(char face, char d) {
    switch (face) {
        case 'U': move_perm(U_perm, d); break;
        case 'L': move_perm(L_perm, d); break;
        case 'F': move_perm(F_perm, d); break;
        case 'R': move_perm(R_perm, d); break;
        case 'B': move_perm(B_perm, d); break;
        case 'D': move_perm(D_perm, d); break;
        default: ;
    }
}
// END MOVE THE CUBE

int is_solved(void) {
    int i, j, k;
   
    for (i=0; i<6; i++) {
        for (j=0; j<3; j++) {
            for (k=0; k<3; k++) {
                if (cube[i][j][k] != i) {
                    return 0;
                }
            }
        }
    }
   
    return 1;
}

int read_color(void) {
    char colors[] = "WOGRBY";
    char ch, *ptr;
   
    if (fscanf(spoj_p_in, " %c", &ch) != 1) return -1;
   
    ptr = strchr(colors, ch);
   
    if (!ptr) return -1;
   
    return (int)(ptr - colors);
}

int read_cube(void) {
    int color;
    int i, j, k;
   
    for (j=0; j<3; j++) {
        for (k=0; k<3; k++) {
            ReadColor(0, j, k);
        }
    }
   
    for (j=0; j<3; j++) {
        for (i=1; i<5; i++) {
            for (k=0; k<3; k++) {
                ReadColor(i, j, k);
            }
        }
    }
   
    for (j=0; j<3; j++) {
        for (k=0; k<3; k++) {
            ReadColor(5, j, k);
        }
    }
   
    return 0;
}

int main(void) {
    spoj_init();

//    spoj_p_in = fopen ("cases.txt" , "r");
//    spoj_t_out = fopen ("solve_old_pochmann.txt" , "r");
   
    int d, n, t;
    int len;
    int score = 0;
    int skipped_all = 1;
   
    char move[4];
   
    if (fscanf(spoj_p_in, "%d", &t) != 1) return SPOJ_RV_IE;
   
    while (t--) {
        if (read_cube() == -1) return SPOJ_RV_IE;
       
        if (fscanf(spoj_t_out, "%d", &n) != 1) return SPOJ_RV_NEGATIVE;
       
        if (n == -1) {
            score += 1000;
            continue;
        }
       
        if (n<0 || n>1000) return SPOJ_RV_NEGATIVE;
       
        score += n;
        skipped_all = 0;
       
        while (n--) {
            if (fscanf(spoj_t_out, "%3s", move) != 1) return SPOJ_RV_NEGATIVE;
           
            len = strlen(move);
           
            if (len == 3) return SPOJ_RV_NEGATIVE;
           
            if (!strchr("LRUDFB", move[0])) return SPOJ_RV_NEGATIVE;
           
            if (len == 1) d = 1;
            else if (move[1] == '2') d = 2;
            else if (move[1] == '\'') d = 3;
            else return SPOJ_RV_NEGATIVE;
           
            move_face(move[0], d);
        }
       
        if (!is_solved()) return SPOJ_RV_NEGATIVE;
    }
   
    if (fscanf(spoj_t_out, " %c", move) != EOF) return SPOJ_RV_NEGATIVE;
   
    if (skipped_all) return SPOJ_RV_NEGATIVE;
   
    fprintf(spoj_score, "%d\n", score);
//    printf("%d\n", score);
   
    return SPOJ_RV_POSITIVE;
}

It's written in C, just like SPOJ requires. For security reasons, I wont paste the current judge, which generated random moves.
 

AlphaSheep

Member
Joined
Nov 11, 2014
Messages
1,083
Location
Gauteng, South Africa
WCA
2014GRAY03
Haha... Programming contests always attract the sorts of people who won't settle for worse than a perfect score. I bet he's not even upset about being disqualified. It's more about figuring out a solution and that awesome feeling when you get it to work than winning the competition anyway.
 

campos20

Member
Joined
Dec 26, 2015
Messages
36
Location
Brazil, MG
WCA
2015CAMP17
YouTube
Visit Channel
Haha... Programming contests always attract the sorts of people who won't settle for worse than a perfect score. I bet he's not even upset about being disqualified. It's more about figuring out a solution and that awesome feeling when you get it to work than winning the competition anyway.
I think he got upset. Later, he sent me a message. Perhaps a swear-word in his language.

saftaj ga
 
Top