Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

neal's blog

How randomized solutions can be hacked, and how to make your solution unhackable
By neal, 6 years ago, In English

Hi Codeforces! In Round 507 earlier today, a large number of "mostly correct" randomized solutions on 1039B - Subway Pursuit were hacked. I wanted to write a quick explanation of how it's possible to hack these, as well as a guide on how to write your code so that you aren't vulnerable to getting hacked.

First to go over the solution quickly (skip down a few paragraphs if you already know the solution): one can use binary search to reduce the range of possible locations for the train to a constant multiple of K, such as 6K. Just make sure to expand out both ends of the range by K after every iteration. Once the range is at most 6K, one can repeat the following:

1) Make a random guess out of the remaining numbers. The probability of success is at least .

2) Binary search again until the range is at most 6K again. It turns out this only takes one query, since after our previous guess our 6K range will become an 8K range, and a single query will reduce this to again.

Since K ≤ 10 and we have 4500 queries, this works because our probability of failure on any test case is at most , extremely low.

However, this makes a key assumption that the train locations are independent of your queries. The main problem that most hacked solutions had was being completely deterministic; i.e., the programs query the same sequence of numbers on every run, given the same output. Most people had this issue due to using rand() without ever calling srand(). There were a few other causes as well: random_device is oddly deterministic on Codeforces, as is mt19937 without a seed. Calling srand() with a fixed value is no good either, as the program is still totally predictable.

Because of the predictability, these programs are quite easy to hack: simply generate the same sequence of queries that the program would make, and set up the train to always be at a different location from each query. To make this even easier for yourself when hacking, you can choose N = 2 and K = 1, which skips the initial binary search phase, and then literally move the train to the non-queried option between 1 and 2 every time.

Workaround?

To get around this, many competitors seeded their generators with the current time by calling srand(time(NULL)); This stops the code from being deterministic and makes it less likely you will get hacked, but it turns out this is still very possible to hack. How? The main problem here is that time(NULL) is only precise to one second. So if I'm able to guess the second that your program gets run, your program is effectively deterministic.

It turns out I don't even need to guess. If I set up N = 11 and K = 10, I can produce all the different query sequences you might generate in the next 10 seconds, since your code will almost certainly be run a few seconds after my generator. Then for every query, at least one of the 11 positions will not be chosen by any of the 10 sequences, and I can move the train to that position each time. Unfortunately -- or fortunately for the people in my room ;) -- I didn't have time to do this during the contest.

Solution

The fix is quite easy. time(NULL) has the right idea, but we should use a much more high-precision clock:

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

Then generate random numbers by calling rng(). Remember to include <chrono> and <random> for this.

Another option is to use the address of a newly allocated heap variable:

mt19937 rng((uint64_t) new char);

This should be different every run. Note this creates a tiny memory leak for the life of the program since we never call delete, but since it's just one variable it's not a big deal.

I personally like to combine both of these methods, but it isn't necessary. Either one will give your program much more unpredictability, making it effectively impossible to hack.

Thanks for reading! This will likely lead to me getting fewer hacks in the future, but I thought the community should have a guide explaining this unusual situation.

If you want to read more, take a look at dacin21's great post on anti-hash tests.

  • Vote: I like it
  • +271
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it
I can generate your query sequences for the next 29 seconds (since your code will almost certainly be run a few seconds after my generator). Then for every query, at least one of the 30 positions will not be chosen by any of the 29 sequences, and I can move the train to that position each time. Unfortunately -- or fortunately for the people in my room ;) -- I didn't have time to do this during the contest.

This exact approach doesn't sound safe. K is too small, so it is possible that after some move you are "trapped" because you need to jump too far away from your current position.

You can make it work for sure by taking smaller N (11 sounds good, so the time window will be 10 seconds), or by taking large N and limiting your time window to 2K seconds while making moves somewhere in the middle — to be sure that after each move you have 2K + 1 available positions to go and aren't restricted by the end of array on either side.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good catch, thanks! Updated the post.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

your posts are simple, and educative...worthy to read

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it -27 Vote: I do not like it

I think rand and mt19937 are not different in practice. Could you provide a problem in which rand() fail?

Edit: I'm wrong.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    What is this abomination? If you want to combine multiple calls to rand() to get more bits, shift and xor them. That will be exactly as bad as the original rand(). This is much worse. This weird function you posted has a significantly biased output. For example, rand()*rand() is more likely to be 0 than any other of the possible outputs; and there are many outputs in its range that will never be returned.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    you also have overflow in the second term

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

1) Using srand(time(NULL)) AC

2) Using mt19937 rng((uint64_t) new char) WA 103

3) Using mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) WA 103

I am not able to figure out if there is a bug in my code.

And also just a question about finding the probability of soln passing. P(pass) = 1 — P(fail) and P(fail) can be calculated. Can we directly calculate probability of soln passing given that 1/60 would be the chance in one query.

Thanks for the great post btw!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are still using rand() in your code version 3. Instead you should use uniform_int_distribution<long long>(L, R)(rng);

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    And to the question about the probability:

    Yes, of course you can compute it directly. One way would be, compute the probability that it passes during the first attempt , that it passes exactly during the second attempt , exactly the third time , and so on, and add them all up.

    Then you get . Here p and q are the probabilities of fail and pass. You see, you get exactly the same result.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea why this failed systest and passed in practice? Is it just bad luck?

PS: Is it just me who is unable to use "Codeforces tags" in comments (the dropdown gets hidden behind text box)?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Yeah, bad luck: Suppose k equals 0, the target is 1 and your current interval is [1,2]. There's a 50% probability of you querying the interval [1,1] as part of your binary search. If that happens, you'll get "Yes" back, which (ironically) means that you lose because you don't stop immediately after guessing correctly.

    → Reply