V--o_o--V's blog

Hack Protection LLC
By V--o_o--V, history, 6 years ago, translation, In English

Remember http://codeforces.me/contest/1039/problem/B or http://codeforces.me/contest/843/problem/B and the hack fiesta with reproducing the pseudorandom sequence?

It might be the case that some of you don't want to be seed hacked. There is a post by neal about the issue. The post is well written but I strongly disagree with the solution described there.

"This should be different every run." I'm fairly sure that it indeed is (well there is still is a small probability of collision but this is kinda obvious). Because of that you are no longer able to conveniently debug you program.

You can hide that under an IFDEF and this fixes the aforementioned problem. However hiding the code under the IFDEF takes 3 lines of code and you may accidentally change something in the IFDEFed part and never notice that locally (the latter is somewhat made up). And I consider IFDEFs ugly but it is a personal thing.

Another way is to obfuscate the generation of the seed. It is definitely against the rules though. There are some grey area ones like hashing a string of tabs and spaces.

There is another way.

template <size_t S>
constexpr bool ls(const char a[S], const char b[S]) {
    for (int i = 0; i < S; ++i) {
        if (a[i] != b[i]) {
            return a[i] < b[i];
        }
    }

    return false;
}

static_assert(ls<8>(__TIME__, "18:50:00") || ls<8>("20:15:00, __TIME__)", "((");

I don't think this requires any further explanation. It does not compile between 18:50 (should be shortly after the submission) and 20:15 (should be the time you expect the contest to end). This was tried on the Educational Codeforces Round 54.

Initially the hacking attempt received something along the lines of "Invalid Verdict". Later the solution and the hacking attempt were ignored (we were deemed trolls or smth like that). However, this is somewhere in the grey area. It might be considered an attempt to destabilize the testing system but I assume that the testing system should be fine.

It is not known how will similar submissions be treated in a standard contest. While I do think that hacks are cancer and would never hack myself I understand that in almost every problem the hack is beneficial to the hacked person. Therefore I am not willing to try this code in a Div1 contest unless there is a problem with a randomized solution. However, someone might and I would be curious to see the results.

Irrelevant Fact

The actual reason for my preference of this approach to any other is because it seems like a middle finger one to a person who tries to hack the seed but without resorting to swearing. Feels good man.

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

»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Auto comment: topic has been translated by V--o_o--V (original revision, translated revision, compare)

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

Pretty creative. But such solutions, of course, will be considered a violation of the rules. As they waste my time, I will punish such experimenters. If there are annoying multiple attempts, then I will simply count the hacks on such solutions as successful. Probably, I'll use a compilation cache to reuse binaries from the judgement process.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +119 Vote: I do not like it

    In my opinion, there is no need for a compilation cache. Here's my argument:

    1) A submission survives a hack iff the result of compiling the submitted code and running the program on the given input is the expected output (considering time and memory constraints).

    2) Therefore, if compilation fails, the process described above can't possibly print the expected output.

    A compilation cache would help the submitter (unjustly, in my opinion), but the rules work fine without adding a special case.

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

    It is of course a violation of the rules, but it aims at a real problem.

    Randomized algorithms are recognized by the computer science world as completely valid algorithms, and I hope they can be used in contests. However, hacks on such problems result in a mess. Solving a problem or not depends not only on whether I can invent and code a solution, but also whether I know the quirks of defending against hacks and on having in my room someone who would craft a test (of real frequency of 1 in 10100) that fails my solution. Some of the defending techniques (like obfuscating the constants) are rules violation too.

    Of course, we can't allow the above hack, but can we maybe get some other way of defending against crafted tests? Things that come to my mind are:

    • running the same code once again after some (long enough, random) time,
    • providing a random number generator that won't be predictable by hackers,
    • providing a random seed (via argv[1] maybe?),
    • making time() return incorrect values (possibly consistent, to allow for time measuring).
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +58 Vote: I do not like it

      I don't think it is a real problem. Just adding this to template is enough:

      #ifndef LOCAL
unsigned seed = random_device{}();
#else
unsigned seed = YOUR_OWN_AWESOME_SEED;
#endif

      (random_device is not 100% guaranteed to be non-deterministic random, you can use time in milliseconds to be absolutely sure).

      I personally agree, that solutions with srand(fixed_value) should pass, but it's very easy for participant to fix such solution (if it's not, when participant will find out something new about how randomized algorithms should work and how to generate good seed) and impossible to find perfect way to "fix" that from the jury side.

      For example, hacking standard library containers is more serious problem, one can not be defended from that is such a simple way.

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

        random_device in MinGW produces the same numbers all the time, so you'll be easily hacked (:

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

          Ok, didn't know that. Let's use high precision time, it doesn't change any of my points :)

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

            It kind of supports my point though. You are a strong and experienced contestant. You are aware of the possibility to hack a pseudorandom solution that uses standard (and not safe enough) randomness. Yet, your suggestion falls to the same kind of trick.

            This is the fallacy I'm describing. A problemsetter hopes to challenge contestants with finding an algorithm, not with knowing the exact specifics of the random_device implementation of MinGW compiler.

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

              My main point is that there is no magic button "do not allow hack which abuses specific pseudo-random generator or some properties of codeforces testing pipeline". Maybe contests would be better with such possibility (or maybe not), but it is not possible to save participants from such traps. For example, all your suggestions do not help if contestant didn't call srand at all.

              About random_device: I initially wrote that is not guaranteed to work (forgot that codeforces servers use cool c++ compiler though). If I would be hacked with such code, it would be my problem, not jury problem.

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

      Modern C++, I think, has enough ways to generate unpredictable random numbers. And the second and the fourth methods are not that easy to implement (especially to be used with other languages).

      There was a similar discussion (in Russian), not about randomized solutions, but about precision issues. In short: the tests for 404 C were made to fail solutions with double. The argument was like

      Randomized algorithms Algorithms with floating point numbers are recognized by the computer science world as completely valid algorithms

      But we write not abstract algorithms, but real programs, so we should know which tricky cases we should care of if we use some techniques or library functions [by the way, does anyone remember this interesting hack of Arrays.sort in Java? :)]

      In the ideal, if anyone would be hacked on random that is not random enough, he would go to his favorite search engine and find out the ways to write randomization better. But it's better than your third option, because in it you also need to be aware of a safe way to initialize random (learn about chrono::steady_clock and friends in my case and about random seed in argv[1] in your case).

      The first option slows down the process, which is also not good.

      So, the best advice I can give is to learn more about the things that you use. Randomized solutions are not only the cases when you can meet with some unexpected hacks (see the examples above, there may be much more of them). Would you want to patch all such cases on Codeforces? :)

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

        And the second and the fourth methods are not that easy to implement (especially to be used with other languages).

        The fourth one requires changing system clock to a random date. It doesn't matter which language it uses.

        There was a similar discussion (in Russian), not about randomized solutions, but about precision issues. In short: the tests for 404 C were made to fail solutions with double. The argument was like

        Algorithms with floating point numbers are recognized by the computer science world as completely valid algorithms

        There is a whole computer science field, numerical analysis, which deals with estimating precision of various algorithms doing the same thing and distinguishing the more precise from the less precise ones. In competitive programming it rarely matters (with the exception of using integers when possible to avoid precision issues) but that's because problemsetters rather don't design problems to check this knowledge.

        If a problem is designed to check it, it's understood that many people will fail it. But it is possible (and often done) to design a problem that deals with floating point numbers and doesn't require this knowledge. On the other hand, I can't think of a way a problemsetter can require coming up with a randomized algorithm while allowing the contestant to not be aware of hacking pseudoranom solutions.

        In the ideal, if anyone would be hacked on random that is not random enough, he would go to his favorite search engine and find out the ways to write randomization better.

        The checker doesn't write "your pseudorandom was not good enough, try again". If I see my solution fail, I look for a bug in the code, not for a way to use another random number generator. Sure, it's my fault then, but it's not as easy as you describe.

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

      Well, as a counter-argument, C++ is notoriously not a precise model of computer science. C++ is full of such quirks, we just familiarized ourselves with the fact long before becoming successful in programming contests.

      In most other languages (I've just checked for Java, Python, and D), when you just start using random numbers, they are already conveniently initialized by a seed which is more or less unpredictable (at the very least, milliseconds of start time are used in the seed, which makes most contest hacks infeasible). The mess here is more or less exclusive to C++, and MinGW for that matter.

      But that's what C++ is: it is very powerful, it can do anything, but at the cost of every single thing requiring a bit of knowledge and effort. In the balance of power versus convenience, why would random numbers be any different?

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

    But such solutions, of course, will be considered a violation of the rules.

    I think that in this case the rules should be updated, because now it (at least formally) can't be considered violation of rules. [Just read https://codeforces.me/blog/entry/4088 carefully :)]

    By the way, the trick is really interesting :)

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

      I think it is a violation of rules:

      You are forbidden to perform any other actions that can in any manner destabilize the judging process.

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

        Maybe it can be considered destabilizing, but I think that destabilizing here means making the system crash, significanly lag or become unavailable, but not exploiting this oversight, which doesn't affect the stability of the system.

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

          Okay, now I see that no one accepts my point of view, but nevertheless I will try to explain what I say.

          IMO, destabilizing the judging process means all actions that will interrupt this process from the participant's side. For example, this case (when participants forbids to compile his solution in some time segment).

          Formally, using such asserts, the participant just says: "you cannot test my solution until I don't want it".

          I.e. for me it seems like stopping the judging process of his solution until he wants it.

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

            Now got your point of view, it also makes sense. But, in my opinion, but such things or explanations what "destabilizing" means should be written in a more explicit way.

            This "hack" can also be fixed in a pure technical way (see below).

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

    I think the hack should just receive "Compilation Error on hack 1" verdict and be successful

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

Hacks are devastating, I approve

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

So, why hacks still exist???

→ Reply