I'm sorry for my curiosity, but I really would like to know.
What happens to Žiga Željko in IOI 2015?
I remember he gets 100 in problem scales very quickly but not long after that, his submission becomes 0. In IOI stats page, his score are dashes (-).
I believe he is accused to be cheating. Can anyone (especially ISC, or those who attend GA) confirm this? What did he do?
At first I suspect the easiest way to cheat happens, the leader spoil the problems to the team. However, if that's the case, the rest of the team should be disqualified as well. That's not the case, so I have no idea.
Anyway, I am not related with any Slovenian team. I just curious.
As was confirmed to me by several sources, he was disqualified.
Official answer ends here. Everything below is not an official answer and might be incorrect.
According to the information I have, it looks most likely that he violated at least the second part of the following rule:
contestants must not attempt to submit illegal programs as discussed above, nor try to tamper with or compromise the grading system,
which would explain the reevaluation of his submission on scales from 100 to 0. Since he was also disqualified, I would guess that ISC judged at the end of the day that it contained malicious intention. Although it would be nice to hear technical report on this and why/how it occurred to aid in prevention of similar cases in the future.
I've heard that he used some undocumented functions in the grader that made it possible to do weighings without increasing the counter that determines the score.
Maybe he discovered the answers using 0 weighings, which is of course very suspicious...
If he indeed found a way how to use grader's mistake then disqualification is a very unfair action of jury. It is 100% judges fault that grader allowed exploiting it in such way and punishing the contestant in this situation doesn't make any sense.
If I found a way to exploit grader during the contest, it's highly probable that (if I had enough time of course) I would also spend few minutes on sending this into testing system and writing judges a message describing exploit in case of success.
The emotional text above is legit only in case if everything was how pllk described. Can anybody provide some extra information about this case?
I looked at the grader (sauce: Yandex mirror); it has no special "undocumented functions" in it. It doesn't, however, have any security precautions (maybe there's a secret one that does have them), which doesn't seem like a mistake. It's more probable that there's simply no need to bother with making it impossible to bypass the grader system when it's explicitly forbidden by the rules.
The key is in informing the jury right after getting 100. If he did do that (directly or indirectly asking for that submission to be skipped), then it would be unfair IMO as well; otherwise, not really — it indicates intent to cheat and not just to test something out, even if that's already against the rules.
There was a long delay before his submission was re-evaluated from 100 to 0. I don't believe it took ISC about 1.5 hours to figure out that something dodgy was going on, especially because I imagine ISC looks at some of the submissions and first 100 in a task is likely to be one of them. Perhaps the ISC was giving him the benefit of the doubt and waiting to see if he would notify them. I personally don't believe disqualification is a reasonable measure for someone who exploited the system during the contest and notified the organizers so that it can be fixed (as long as the exploit doesn't impact other contestants), so I would be very surprised if he notified the jury before re-evaluation to 0 and got disqualified.
My leader said (I still don't know the details) that this contestant reverse-engineered the offline judge to see how it worked.
If I remember well, he rewinded the input (it was a file I think) to read it by himself and so he knew the answer to the problem without calling any functions, and that gave a 100 / 100 (in fact, it should give an infinite amount of points :D). Maybe he did other stuff to make his submission less suspicious.
I agree with you Zlobober, I think he should have had his points, or at worst he should have a 0 on this one. It's the ISC fault if something like that was possible.
Even if it's forbidden to do that, it's something you want to try, and if you get the points...
Well, after this example, it's something you don't want to try :D
Yes sure :D
I didn't say exactly what I had in mind: I should have said : "If you somehow find a solution which gives points even if it doesn't really solve the problem, than you should not be penalised too much."
It's not something you should try to do at first, it's only OK if you find that way by chance, by looking at the grader code to see how it works or something like that.
But in fact, he was disqualified after TWO hacking tries, see misof's answer, so he really did not want to try to solve the problem, and it's logical that he was disqualified.
Yeah, my teammate peto159 talked with them (I think...) and he told me the same.
We came up with another idea that might "hack" those interactive tasks (none of us tried it, of course — but maybe some ISC guy reads this comment and tries/fixes (if necessary) it for next year):
IOI 2015 is the first IOI where multiple threads are allowed. So it is possible to fork and solve the problem in the child process with a suboptimal amount of queries — then return the result to the parent process, which submits the answer with 0 queries. I think that should work, because the child process has seperate variables (and basically seperate anything), so the parent process has no chance to know about those queries, right?
Here's a quick proof of concept (I even added a lot of comments ^^): here. The codes printes the following on my mac:
Would something like that have worked?
UPD: Well, the more I think about it: Forking isn't the same as a thread (haven't really realized that at the time of writing the comment.. probably because I don't know too much about this kind of stuff ^^) — so maybe it's not even possible to call fork. Does someone know more?. I'm kind of curious :)
No, forking is not the same as creating a thread. Fork create a child process with a copy of the parents address space, while a thread is a "lightweight process".
Threads are usually created over a function and multiple threads running that function mean multiple calls of that function working in parallel. Threads share the same address space so that's why you must make the function thread-safe.
And also threads are much cheaper to create than processes, because of the above mentioned. :)
Ah, that makes sense! I should have thought of that. Stupid me — I even remember being taught that stuff at school again :) Thanks!
So I guess forking wouldn't work at IOI after all, right?
C++11 <thread> library didn't work at IOI practice session (pthread wasn't linked). I don't know if they fixed this for the real contest, but I sent a clarification about this and they never replied, so I assumed some other way of multithreading (or effectively multithreading) that I didn't know of was working.
In Linux all threads are created using exactly the same system call as processes. You just have to explicitly specify that you want the same address space. All the pthread* stuff is just some high-level wrappers around
clone()(manpage) system call. So if you can create thread you pretty much can create process.Yes, he was disqualified.
First of all, a clarification. The ISC did not disqualify the contestant. After contest day 1, the ISC has gathered the evidence, presented it to the IC (the international organizing committee), and the decision to disqualify the contestant was the result of a vote in the IC.
As for some technical details, during the contest the contestant came up, sequentially, with two different ways of hacking the grader. The first attack happened at compilation time and involved a clever trick with #include and #define. This was the one that was visible in the ranklist for a while as 100 points. After discovery of the attack he was told not to do so and provisionally allowed to continue solving. The second attack happened afterwards, and was based on forking during the solution's runtime.
In one of the comments on this post, Zlobober says the following: If he indeed found a way how to use grader's mistake then disqualification is a very unfair action of jury. It is 100% judges fault that grader allowed exploiting it in such way and punishing the contestant in this situation doesn't make any sense.
Regardless of the fact that the previous post he responds to is incorrect, even if it were correct, I would still wholeheartedly disagree with his statement. Such an action by the contestant goes both against the letter of the rules (where it is clearly stated that the type of actions is forbidden) and against the spirit of the rules (as it is clear that the contestant is not attempting to solve the given algorithmic problem).
On the other hand, the sentiment in Zlobober's second paragraph (_... and writing judges a message describing exploit in case of success_) is something that might have changed the situation, at least in my eyes. This is something that did not happen in this particular case.
Additionally, I would personally see a huge difference between doing this in the practice session and doing it in a real contest. By attempting to hack the grader you are not just jeopardizing your own results, you are also influencing the actual contest for the other contestants. At the very least, your actions will consume some time of the scientific committee members, and this then has other effects such as later answers to other contestants' questions. It is also possible that the process of repairing the damage you've done will require a rejudging of a particular task, which then unnecessarily increases the judging queue and thereby the judging response times. To most contestants, the IOI is a very important contest, and disruptions such as increased judging time may affect their performance for the worse. And even though everybody else is affected in the same way, the net effect will be different for different contestants. There are good reasons to have rules that forbid and penalize this kind of behavior.
It is clear that the contestant's actions were intentional. It is not clear whether that intent was malicious -- and this is why, to many of us including myself, the decision whether to disqualify the contestant seems to fall into a grey area. It is my personal opinion that in this particular situation the IC made the right choice -- by choosing the lesser of two evils. Given the current competition rules, the choice was essentially between "do nothing" and "disqualify". I was not present at the IC meeting, but as far as I can tell, the main factors behind the disqualification were the obvious intent, the lack of evidence that the intent was not malicious, and the message the IC wanted to send to future contestants. The rules are in place to protect the integrity of the contest, and it is a good thing for the contest to enforce them.
I agree that the actions taken in this case (to the extent that I understand it) by the IC and ISC were reasonable and right.
There are however a number of other practices for which I think rules should be made clearer.
At present (or at least back when I was a contestant) there are several ways in which one may use the submissions to gain information about the test data. One possibility for example is to use "assert" statements. My understanding is that this practice has even revealed bad test data during contests in the past yet it is in my mind not exactly in the spirit of the contest.
Another way instead of using asserts would be if a contestant tried to use "TLE" as a way of gaining information about the input (by making the program terminate or go into an infinite loop depending on some property of the input). It is unclear to me whether the rules at present would give grounds for disqualifying the contestant who tried to use such submissions to gain information about test data "in good faith" (in the sense of each submission really trying to extract the information instead of just trying to slow down the grader) but still ended up making 80 submissions of such type.
(To be specific — suppose there is a task with only three ints as input. I can use 96 submissions of the above variety to in effect learn all the inputs. I then use an inferior algorithm to actually compute the outputs and finally submit a program with all these answers hardcoded for 100 points.This entire process can be fully automated. Cheating or not?)
In my opinion this is completely fine and shouldn't be punished. I've used TLE and WA to find stuff about tests (not on IOI, but on some other competitions). This has helped me find faulty testcases and sometimes, though it might be considered "not in the spirit of the contest", it has helped me pass this one horrible test that would kill my whole subtask.
This year's IOI however had a lovely precaution against that — you would get information only on the number of tests having some verdict, and not test-by-test results. So you would for example get "10 WA and 5 TL" as your full feedback. In the practice session I actually had some bug on problem graph that would give me 2 WAs on the largest subtask, and using submissions that would hash the input and then try to find that hash I actually got full score, so the system is obviously not absolutely unbreakable, but it is significantly harder to get information about test data.
In whatever way ISC decides to give the feedback, I think that such submissions should be perfectly fine, and test data should be created in order to stop people from getting any useful information using such submissions.
P.S.
An official response or better clarification of what submissions are allowed would be nice though, because with the current rules it is not clear whether such things are considered cheating.
Thank you for the answer. From your words it becomes much clearer why one can tell that he deserves such punishment. Let me clarify my words you quoted above.
Suppose that I found a way how to hack a contest environment, or grader, or compilation process, or whatever, to get score in an unfair way. First of all, I think that in this situation I must tell judges about that. Otherwise it can simply be that someone else finds such an exploit and uses it for his own benefit and jury can possibly miss such case (after all, jury are also people with about the same skills and abilities as the most skilled contestants). As a contestant I want such situation not to happen because this can affect my place in a final scoreboard.
That's why I would decide to tell judges about this exploit. After that I have two options. I may want to be sure that my exploit works by sending it in testing system and then write judges a message like "Here, look on my 100 points! They are unfair, please fix the hole in your grader and discard my score on this problem, so I can write a fair solution". On the other hand, I may just write "There is a potential exploit in this place, ...".
What I want to say is that there are reasons to choose first way rather then second. First, it may appear that the wrong person reads my message and he is not able to understand what I'm talking about. It may be that he tries an exploit by himself in wrong way and it doesn't work for him. It may even be that he decides to check it after the end of the contest because there is a lot of more important work to do now (and after that he can forget about it or find out that 10 contestants successfully used an exploit). That's why preparing a certificate of a working exploit is a reasonable action in such situation.
I understand that this violates the rules you quoted, but I'm curious what would happen if the situation was like I describe above. I'm interested mostly because there are lots of stories available on the Internet about people who find exploits and security issues on large popular sites like github.com, facebook.com, vk.com (our largest social network), some banks sites and many others. There also usually raises a question if such person should use an exploit as a certificate of that he tells the true. The interesting fact is that the behavior of different companies may be completely different. If you do not provide a certificate, you may even not be heard because you'll stuck in a support team that doesn't even understand any single word you are telling. If you decide to provide such certificate (by posting something on the web-site or creating $5 on your personal account) you may be rewarded for your help, as well as you may face threats of suing against you because you hacked their site.
Also as a programmer who is interested in how such exploits work I feel a bit upset that somebody was punished on a programming competition for showing extraordinary skills in just another area of programming. That's... well, that's not a reason for those guy to be justified, but he can do cool things, it's a pity that everything ended up in this way (even though it was intentional as you said several times).
Well, now he can put into his CV the line "I was disqualified from the IOI for successfully hacking the grader." and it may even help him start a career in IT security :)
At the IOI there is "analysis mode" after the contest, and that would be the proper time and place for the activities you talk about. During analysis mode one can not only write the exploit, verify that it works, and notify the jury, but it is also possible to file an appeal with the jury asking them to make sure that nobody gained unfair points by using the discovered security hole. (Even if nobody did file an appeal, a simple notification would still lead to a thorough investigation.) The results are only final after all appeals have been resolved.
As I contestant, if I were to stumble upon something I would perceive as a potential security issue during the contest, the most I would do during the contest would be a quick message to the jury. There's absolutely no reason to waste my valuable contest time on writing an exploit -- as you were just saying, there's more important work to do, namely solving the actual tasks.
I'm not talking about this particular case, but IMO submitting solutions which don't attempt to solve algorithmic problem generally doesn't violate the spirit of the rules. E.g., if someone manages to fit into TL an overly optimized brute-force C++ code instead of implementing complex algorithms, is it really bad?
IMO situations when a participant uses knowledge about low-level stuff instead coming up with high-level algorithmic solution only add fun to programming competitions.
I agree. When I was saying "algorithmic problem", what I had in mind was that the problem they are asked to solve is algorithmic in nature. I did not talk about a specific intended algorithm. My point of view here is that we set the limits, and we ask the contestants to come up with an algorithm and then with its implementation, and the implementation should be correct and work within the stated limits. As long as it does, it deserves the points. What you just described is perfectly fine in my book -- and in fact does happen pretty frequently (e.g., optimized n log n versus linear, or optimized sqrt versus log).