MATLAB Programming Contest BlogApril 8th, 2006ObfuscationWe’re awarding a Defogger Prize to Jim Mikola, whose entry Defogged_8 broke through 10 hours of deobfuscation and took first place at about midnight last night. Descendants of his clear code held the top spot for about 10 hours before we were plunged back into the scramble. In some circumstances, there seems to be a performance benefit to obfuscation. We’re still trying to track this down. If it’s true, it makes it hard for the clear code to stay on the top, even if we have diligent deobfuscators (human or computer). We’re looking for suggestions. Should we disallow obfuscation? If so, what criteria should we use to judge, e.g. is using one-letter variables an example of obfuscation? We’d also like to hear from the obfuscators, who are posting with pseudonyms. What is your motivation? Why do you think this should be allowed? Would you be happy if we made the Twilight phase longer next time? Please leave us your comments. 15 Responses to “Obfuscation”Leave a Reply |
|
|||
|
These postings are the author's and don't necessarily represent the opinions of The MathWorks. |
The obfuscation speed-up appears to be inherent to MATLAB itself, since I see it during testing on my personal computer prior to submission to the contest queue. I believe this is due to shorter variable names and less whitespace for some reason impacting the JIT. If you profile such code you see the speed increases come from the ‘overhead’ categories. Thus the only way to deal with this is via contest rules / mechanisms. A few suggestions:
-All ‘commands’ must be on a single line. A simple check for a CRLF after each ; would help with this. Likewise checks to ensure special commands like end and break are on there own lines and commands like if, while, for start a line would help.
-All ’structual’ commands (e.g. if, for, while) need to be indented at least 1 whitespace from the previous line like the MATLAB editor naturally does. This could be a simple programmatic check in the queue.
-Prior to executing the programs, the queue could run ALL code through an automatic variable renaming program to make all program’s variable names the same format during testing. This is hopefully would make ALL codes see the speedup due to shorter variable names.
-Something should also be done about contestent’s ’spamming’ the queue. A simple concept here is that contestents can’t have more than 3 enteries in the queue at any one time. Alternatively, maybe there should be a minimum time limit between contestents code submissions.
I completely agree to Alan. If you implement a code obfuscation checker as m-file and publish it, every contestant can check if his own code will pass the test. A variable renaming program would allow you to automatically identify if a submitted code version was already submitted before exactly the same.
Another motivation against obfuscation could be a bonus for very well written and documented code. If you keep the influence of this bonus quite small, the additional effort for you would not be too large, as you would only have to rate some entries that compete about winning a phase.
Against spammers you should introduce a minimum time between two entries of the same contestant (check ip adress of submitting machine), e.g. ten or fifteen minutes. I am sure that there are very fast programmers amongst the contestants, but I don’t think there is one who can make significant changes in less than that time.
In your FAQ you write that the score a submission attains is subject to a certain amount of random noise. Maybe you could let every submission that has chances to get on rank one let run through several times in order to minimize the random influence. This would also take the motivation for submitting the same code more than once.
I agree with Alan’s comments.
Running all submissions through some obfuscation program before testing would hopefully eliminate the performance benefits.
I’m not sure if these entries are being automatically submitted or manually submitted (some are coming in 15 seconds apart). Maybe adding a “Spam Prevention” like you do on this comment list would help with multiple submissions.
Regarding ’spamming’, I would be affraid for too much limitation. The contest is not only about “smart coding”, but also about tuning to the testsuite. If the contest last a week, “tuning” is part of “the job”. And sometimes that is done by multiple submissions with small changes.
The “obfuscation” is something I dislike more, but I also think that not soo much can be done with it. It is a pitty that it seems to have positive effect on the result.
Obfuscation is like pornography … hard to define, but I know it when I see it.
Alan Chalker’s ideas about pre-processing the code are excellent; I wish I had thought of them. Are they practical from the MathWorks perspective?
I think most automated spam-prevention measure won’t be very practical. Fast-but-genuine tweaking, especially near deadlines, is critical to the spirit of the contest and would be indistinguishable from spamming. Also, real spammers could easily disguise their entries to look as if they are coming from different sources.
Now that the leader is “clean” again, I would support, albeit sadly, the Contest Team using their judgement to disqualify any entry that they deem to be deliberately obfuscatory.
I would also support “the Contest Team using their judgement to disqualify any entry that they deem to be deliberately obfuscatory.” Obfuscatory entries should be marked as failed. I believe this would return some professionalism to the contest. I don’t think any kind of software filter would work.
1. I really think that the twilight phase must be exteneded; perhaps to 2 days. I think the true winner of the contest should be the twilight phase winner. In the darknees phase, we do not know yet how optimal our code is compared to that of others. In the twilight pahse, we have an idea and can work to make it better. It seems to me that after the twilight period, we enter in a phase of “code optimization only” which is ok but more weight should be given to “algorithm developement” that happens in the prior phases. This is even better for the latter phase.
2. I also think it is a good idea to introduce a minimum time between two subsequent enetries by the same individual. Even if one wants to fine-tune the parameters of his/her code, s/he must do this selectively by first using the given test suite extensively and only submit the top candidates.
Regarging twilight phase, I think it needs to be extended as well. I found out about the Sudoku contest after it entered daylight and never entered anything because I found the flood of code and entries too overwhelming. I think people finding this contest now would find it hard to get interested in it. Giving people more time to work on their own code would, in my mind, result in more people being involved.
Plus, the darkness/twilight time is so short that if people are busy during that time, they are likely to bypass it altogether.
I don’t mind the Obfuscation since it only slows down the community for a short while. I was a little surprised to see a piece of code I submitted in clean form turn up a short while later in obfuscated form. I guess if we can reverse engineer obfuscated code, the opposite can be done as well. It does spoil the spirit of collaboration though.
I think increasing the length of the twilight phase by a day or two is a good idea. It provides more time for individuals to explore their ideas. Once daylight takes hold there may be a greater amount of ideas in the mix.
I pretty much agree with Allan and Markus about the obfuscation and spamming and also with Farhad and Rick about the extending of the twilight phase. However, to prevent the obfuscation a bit more, as well as to make the last phase of the contest more interesting and less optimizing-oriented, the leading-entry’s code and the codes for the entries waiting in the queue, could be hidden.
I don’t think that the twilight phase should be extended; rather the contest should _return_ to twilight for the last few hours. By then obfuscators and spammers had their fun for 5 days, people had the chance to learn about tweaking their code to the contest software and fortunately some piece of fine code has the lead. If we return to twilight then, everybody has the chance to test new ways to improve this highly efficient code, without seeing a scrambled version of taking their solution the lead a few minutes later.
There are two kinds of obfuscation, 1. real development but coded as obfuscation; 2. a copy of an existing code. The first class would have some positive contributions to the contest. But the second should really be ruled out from the contest. This could be done by filting all submissions through an obfuscation software. If it is equivalent to an existing code, then the submission would be failed.
Give one more day for the twilight phase would be good idea. Some idea needs time to develop.
Yes, I too think the twilight phase should be extended. I find it the most interesting and exciting of all the 3 phases. Srach’s idea of returning to the twilight phase for the last few hours is also good.
For the queue spamming, I feel each individual should be allowed to have atmost one entry in the queue at any time. There could be one parameter in my code that needs to be tuned and I can submit 100 different entries with 100 different values for the parameter without putting much thought into it and letting the scoring/testing software do all the work for me and taking up all the queue time which is not fair if others are waiting. so maximum one entry at a time rule seems good.
Personally, I found the contest most interesting during the darkness and twilight phases. In my understanding, the reason for having a daylight phase is to give people a chance to combine ideas. If there was twilight throughout the 7 days of a contest, with three days into it, it is probably too late to start to develop your own entry from scratch. With daylight, you can see others’ entries and join the contest midway through. Obfuscation makes this almost impossible. And if you ignore it, you go back to your own entry, work on it, use others’ ideas, then submit it and others tweak and disguise it, so that noone else could work on it. Very discouraging.
On the other hand, you can’t really fight against obfuscation. If it makes the code faster, well, such is life. The fastest code wins. (Although it is surpising that you can get a 5% speed gain by renaming the variables and removing the withespaces.)
I think it would be great to have one-two-day ‘twilight only’ short contests. Possibly with a rotating schedule, not to disadvantage anybody around the globe. Something like 5 small problems during a week. Scoring, timing could be the same. Maybe there could be a few hours of darkness at the beginning. And maybe a limited number of entries allowed per contestant.
Imre Polik
Returning to the twilight is a very good idea. I suggest to keep the contest in twilight all the time, but separated into several phases. The submitted code is revealed at the end of a phase while new submissions are hidden during the next phase. Then significant algorithm improvements would have greater chances to win than taking code of someone else and tweaking it without understanding the implemented algorithm.
Even when returning to twilight, obfuscation should be absolutely forbidden.