Um_nik's blog

Randomized solutions vs Hacks
By Um_nik, history, 7 years ago, In Russian

I think that most of us know about situation with problem 843B - Interactive LowerBound. The intended solution (and it looks like all possible solutions) was randomized and it generates huge amount of hacks based on fixed randseeds.

I want to mention that I'm not against good randomized problems and I even set one myself.

But for me it seems that hacks can ruin such type of problems. The only thing author's solution is better than contestant's is that it is invisible during the competition. I can even imagine that some tester's solutions (maybe not the solution which is used to generate judge answers) was broken by some hacks.

I think that it breaks the problem as art piece and breaks the contest format too. You solved the problem just like authors wanted and now... it depends on is there a hacker in your room. It also breaks the idea of hacking. There is no bug in my solution, why should I be hacked? And why should the guy get 100 points for hacking me? He didn't crack my solution, he abused CF 'Run' tab.

And for me it looks like authors didn't think about that bug/feature and now they try to protect themselves in comments. For me it could be a good enough reason not to use this problem on CF round. This problem would be a good problem in ACM contest and I know that these guys do ACM contests. But maybe there were a way to prevent such abuse of hack system?

What about forbidding hacking this particular problem? It has two obvious flaws (maybe more).
1. After this post it can give a hint that you should use randomized solution — Yes, this is a problem.
2, All problems should be equal! You are taking away our sacred right to hack!!!1! — Are they? There are a lot of problems with no hacks on CF. There can be many reasons: the problem was too easy, or too hard, or it has no corner cases, or it can be solved only in one way, or, or... You can say that I propose unnatural way to prohibit hacking and in those cases it was prohibited by the problem itself. But (in my opinion) such randomized problem also naturally prohibits hacks because hacks can ruin the problem.

And it is also not true that all problems were 'equal' in this sense before. There were some problems with multitests which allow to hack with only one test in multitest. There can be a bug in handling multitesting but we cannot hack this bug.

This brings us to less cardinal solution: make some bounds on hacks. Like n ≤ 100 or (in this particular problem) let only choose values in list, but not their order.

Anyway, I think that problemsetters and coordinator should think about these matters in the future.

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +62 Vote: I do not like it

... or don't use fixed rand seeds?

→ Reply
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

One good thing about hacks like yesterday's is that they bring latent problems with contest code to public attention. For example, I learned from the comments that:

  1. random_device can be deterministic, at least it is under the particular MinGW implementation used by Codeforces.

  2. It is possible to treat srand (time (0)) solutions as deterministic, just by correctly estimating the time of judging with a few seconds precision.

I won't learn the above if not for the hacking opportunity. Granted, it is not relevant to the pure part of algorithmic problem solving. But programming contests inevitably include implementing the solutions, and that is where such facts get useful.

We can learn from this experience and adapt the default approach. Or we can say "all problem setters who will use these flaws in the future are bad". But many problem setters do weirder things anyway, so it's best to learn not to depend on them being "good" or "bad" in this particular regard.

Finally, with any luck, this discussion will also reach a consensus in how to best get an unpredictable random seed in a contest environment in C++ (is it rdtsc?).

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

    Hash a string of whitespace characters.

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

    I started using microseconds (or even nanoseconds, if available) for initializing the rand seed, which is almost impossible to predict.

    Smth like

      srand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    → Reply
»
7 years ago, # |
  Vote: I like it +40 Vote: I do not like it

I think that it breaks the problem as art piece and breaks the contest format too. You solved the problem just like authors wanted and now... it depends on is there a hacker in your room. It also breaks the idea of hacking. There is no bug in my solution, why should I be hacked? And why should the guy get 100 points for hacking me? He didn't crack my solution, he abused CF 'Run' tab.

Here, I want to clear a misconception about the mechanics of such hacking: there is no need to abuse (?) the CF 'Run' tab.
The example will be my hack against 300iq.
Here is the solution: 29739981.
And here is the hack, with the generating program conveniently shown below.
The important thing is that the generator uses the same language as the submission. If I can write in that language, I don't need to pre-generate the numbers at all. I just have to copy (rewrite) the way the pseudorandom numbers are used, that is, the following lines:

mt19937 rnd(228);
// ...
    int it = 1000;
    while (it--)
    {
        e.push_back(ask(rnd() % n + 1));
    }

As the generator is deterministic, this will generate just the same sequence as the solution. If anything is abused here, it's the deterministic nature of pseudorandom generators, and the ability to write the generator in the exact same language as the solution.

→ Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

The only thing author's solution is better than contestant's is that it is invisible during the competition.

That's not true. The author's solution is better than several (not all) contestant's solutions because it uses a high-precision current system time to generate seed.

In Codeforces the solution get accepted (independent of all circumstances) if and only if it's impossible or nearly impossible to hack it, otherwise it could be hacked. Using high-precision current system time to generate seed is nearly impossible to hack. The fixed seed solution lack this property.

You solved the problem just like authors wanted and now... it depends on is there a hacker in your room.

The intended solution, as I mentioned above, was to use system time seed. If you use fixed seed, I agree, it really depends on hackers in your room. There are multiple types of tasks where getting accepted depends on hackers in your room (for example, problems on strings with hashing or using quicksort without random). I personally don't think there is a trouble with it. If you write an incorrect solution (solution which can be hacked), there always is a chance of not passing tests.

It also breaks the idea of hacking. There is no bug in my solution, why should I be hacked?

There is a bug in your solution. Just use normal seed.

And for me it looks like authors didn't think about that bug/feature and now they try to protect themselves in comments. For me it could be a good enough reason not to use this problem on CF round.

What about forbidding hacking this particular problem?

This brings us to less cardinal solution: make some bounds on hacks. Like n ≤ 100 or (in this particular problem) let only choose values in list, but not their order.

Of course, we knew about this trouble beforehand. It may be not the best problem we could use for CF round, but I personally think it's OK.

We discussed these options and decided that it would be best to allow hacks. With n ≤ 100 or without hacks it's impossible for hackers to fail solutions with fixed seeds. These solution are indeed incorrect, and it's impossible for us to make tests against all such solutions, therefore we relied on hackers to fail them.

We also made tests against some small fixed seeds, but they were deleted.

I also hope that although there may be lots of different opinions on using this problem in CF problemset, you enjoyed the contest :)

→ Reply