[Report] How I caught a cheater

Discussion in 'Software Area' started by campos20, Jan 6, 2017.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. campos20

    campos20 Member

    23
    11
    Dec 26, 2015
    Brazil, MG
    WCA:
    2015CAMP17
    YouTube:
    user/afonsocampos20
    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.

    [​IMG]

    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.

    [​IMG]

    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[j][0]][perm[j][1]][perm[j][2]];
            }
           
            for (j=0; j<4; j++) {
                cube[perm[j][0]][perm[j][1]][perm[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[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.
     
    jfly likes this.
  2. That's pretty ingenious actually!
     
  3. campos20

    campos20 Member

    23
    11
    Dec 26, 2015
    Brazil, MG
    WCA:
    2015CAMP17
    YouTube:
    user/afonsocampos20
    I totally agree. He deserves a medal or something like that. It broke my heart disqualifying him, but his solutions was against SPOJ's rules.
     
  4. AlphaSheep

    AlphaSheep Member

    934
    401
    Nov 11, 2014
    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.
     
  5. campos20

    campos20 Member

    23
    11
    Dec 26, 2015
    Brazil, MG
    WCA:
    2015CAMP17
    YouTube:
    user/afonsocampos20
    I think he got upset. Later, he sent me a message. Perhaps a swear-word in his language.

    saftaj ga
     

Share This Page