2IA7A8E6A7's blog

How to prevent hacks?
By 2IA7A8E6A7, history, 6 months ago, In English

Recently I've had my first hacked problem: 372051449. I didn't really think much of hacking up until this point, but this problem made me rethink. I have a few questions in mind:

  1. What type of problems are most likely hackable?

  2. What are the general methods used to hack a submission?

  3. What preventive measures can be taken to protect a solution from hacks?

I'm interested in your ideas about hacking. Feel free to drop a comment!

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

»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 2IA7A8E6A7 (previous revision, new revision, compare).

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

Bruh, even I can feel your pain, you missed that CM because of the hack.

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I can think of mostly hashing problems and using hashtables (https://codeforces.me/blog/entry/62393) are easily hackable.

→ Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it +7 Vote: I do not like it

You could randomize your base to make it unpredictable

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count() ^ (uintptr_t)(new char));
base = uniform_int_distribution<>(1e8, 1e9)(rng);
→ Reply
»
6 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

That's it I'm using SHA-256

→ Reply
  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it
    1. You don't need 256 bits for anti hash-collision hacks.
    2. You will very likely get time-limit for this because SHA-256 is very computationally expensive. A normal problem with hash maps by using just SHA256 can take a entire second.

    You should use it on a high resolution clock for seed so its faster and you probably won't get hacked.

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

Can you explain me how a problem gets hacked ? sorry idk this :)

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

    You basically submit a test case that makes the code fail, like, for example the code runs on O(n^2) and you use a test case with n=1e6 to make it TLE, or have a bunch of inputs to attempt MLE

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

    Usually, reading from a list is o(n) if you don't know the index because you need to search every item. However, in a hash map (which is a dict), a hash function is used on the item (modulo a number because it doesn't have to be very big) and that will be the index. This runs in o(1)

    A hash collision hack is taking advantage that if 2 items have the same hash (and thus the same index), the program will have to read the entire list to find it (which is very slow compared to hash maps). With a lot of collisions, you can get time-limit on a problem.

    → Reply
»
6 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

use more and larger prime mods.

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

hacks should not be allowed in such questions i feel

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

    This is an F problem though, I do like the idea of hacks, it encourages contestants to be more innovative to find the edge cases (this also applies to real-life applications)

    → Reply
»
6 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

Mostly hashing problems.

Add a random number to the base. Don’t use time(0) for seed, use chrono::steady_clock.

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

Has anyone ever hacked a non-hashing problem? If so, can you tell me about the process of hacking it?

→ Reply