The headline on Slashdot is misleading - as the snippet says, locking and unlocking the device will restore the touchscreen. My guess (having worked on capacitive touch systems) is that the touchscreen doesn't properly recalibrate on a sudden temperature change, resulting in loss of touch detection until the touchscreen recalibrates (which happens every time you unlock the phone). This is easily fixed by a software or firmware change, and has a fairly simple workaround in the meantime.
Unlike what most commenters seem to assume, the phone is not suddenly unusable in the cold - just click the power button to lock the phone and click it again to unlock. Takes less than 2 seconds, after which you can go back to scrolling Facebook in the bitter cold.
If anyone's curious, I've dropped the decrypted contents of the "free sample" up on GitHub: https://github.com/nneonneo/eq.... Hopefully this makes analyzing the collection a bit easier. The code's pretty old - 2010-2013 according to timestamps - but it does look like real exploit/implant code from a distance.
Yes, and it's a fair point that most SSDs haven't been around long enough to even measure their long-term stability. SSD technology has also advanced very far in a short period of time - older generation SSDs are probably also much less mature in technology and therefore more prone to failure.
The SSD manufacturers have yet to see all the ways in which their drives can fail under real-world, long term conditions. I expect long term reliability to improve as companies develop a fuller understanding of the failure modes and countermeasures. For example, hard drives added shock (acceleration) sensors after laptops became commonplace - the failures caused by dropping the hard drive were not previously considered a major risk.
Let's work it out. A few years ago, TechReport ran an SSD endurance experiment to figure out how much punishment current-gen SSDs could take before failing. Their test setup essentially involved writing random data at maximum speed for 18 months straight. The results indicated that the worst SSD in their bunch, a Intel's 335 Series, wrote about 700 TB before dying, and the best SSD, a Samsung 840 Pro SSD, went on to 2.4 PB.
Variousestimates say you can put between 60-75 hours of HD content on a 500GB drive, so, assuming the largest possible size, that works out to about 8.3 GB/hour. Since you're writing two streams, that's 16.6 GB/hour, or 145 TB per year. For the worst drive in the bunch, that's about 4.8 years of service (right at the upper end of your HDD's service life); for the best drive, it's over 16 years.
Keep in mind that these tests were all run on 250GB drives. Smaller drives have less flash to work with, and have to write over the same flash cells more often. Therefore, if you bought a 1TB drive, you can expect the lifetime to be easily 4x better (more if you're using a more recent drive, such as the Samsung 850 Pro) - 64 years of DVR recording should be more than sufficient.
If it really is only $75-120K to crack SHA1, I propose we start a Kickstarter to gather the funds. Given the estimate of a few months, we'll ship our SHA1 collision well before a lot of other Kickstarter projects ship their products:)
Manual car sensors can also be hacked! Shining bright lights at the windshield, especially in nighttime driving conditions, incapacitates the optical sensor of a manually-driven car. Worse, unlike self-driving cars, manual cars behave erratically or unpredictably in these conditions. Even worse, all cars are equipped with hardware that can generate these bright lights, meaning that any car can attack any other manual car in vision range.
Some folks were asking how this works, so here goes:
newgrp is a UNIX utility that executes a shell with a new group ID (UNIX specification page: http://pubs.opengroup.org/onli...). This requires root permission since it can change the group ID to one outside the current shell's group list (e.g. to any group in the uid's group list). Therefore, newgrp is a setuid root application which launches a shell.
DYLD_PRINT_TO_FILE is a dyld (OS X dynamic linker) environment variable that tells dyld where to print debugging information. Ordinarily, dyld supports a large number of debugging options to facilitate debugging shared libraries and to allow neat tricks like DYLD_INSERT_LIBRARIES (equivalent to LD_PRELOAD on Linux). When dyld sees this environment variable, it opens a new file descriptor connected to the specified file. Since fds 0,1,2 are already connected to stdin, stdout and stderr, the file is opened as fd 3.
Notably, since newgrp starts as root, the file is opened using root's permissions, even though newgrp later drops privileges to spawn the shell.
Because DYLD_ environment variables can modify a program's behaviour in unexpected ways, they are usually deleted or sanitized prior to running setuid programs (because otherwise an unprivileged attacker could cause a setuid program to misbehave, exactly as in this exploit). Apple clearly forgot to sanitize the new DYLD_PRINT_TO_FILE when shipping Yosemite, opening this particular flaw up.
Finally, the (outer) echo command tells the subshell spawned by newgrp to execute the (inner) echo command, which outputs the string "$(whoami) ALL=(ALL) NOPASSWD:ALL" into fd 3, which (due to the DYLD_PRINT_TO_FILE variable) is/etc/sudoers. This line tells sudo that *any* account is allowed sudo access, and that no password is required to use sudo.
The subshell then exits (no more commands to run), and the final command "sudo -s" executes. Since sudo no longer requires a password, and all accounts can use sudo, "sudo -s" just immediately opens a root shell without prompting.
Efficiency needs to count programmer time, too. From watching first-year programmers in University struggle with C, to watching seasoned programmers struggle with C, I can assure you that Python wins on programmer efficiency. I've used C longer than I've used Python (~16 years for C, ~13 years for Python), so I am definitely comfortable with both, but I now use Python for virtually all general-purpose programming.
Even when CPU cycles count, I will usually prototype in Python to get all the algorithmic details right before porting to C. Often I won't even port the whole program; a number of my recent projects have had C routines called from Python front-end code (so that the front-end can handle stuff like HTTP requests, text parsing, response formatting and the like).
Finally, libraries like NumPy and Sage are taking Python beyond mere scripting and into the realm of serious scientific programming. It is now possible to write and use complex computer vision algorithms, mathematical algorithms, and heavy-duty number crunching (like MATLAB) in Python, meaning that a good amount of scientific computing is starting to be done with Python instead of more traditional languages like Perl, MATLAB or Java.
Your vbnc was last updated in 2010, and targets Visual Basic.NET 8, which was released with Visual Studio 2005. The VBNC compiler has not had any significant updates since 2011.
Visual Basic.NET is now on version 12. vbnc is horribly behind, and it does not appear to be actively supported. If your instructor were to use any newer language features, such as lambdas, iterators or asynchronous programming, you would not be able to use VBNC to compile that code and would probably have to resort to using Windows somehow.
On the flipside, Python now comes standard with most Linux distributions, and is standard with Mac OS X. It's very simple to install on Windows and even comes with a bare-bones IDE for editing code. In every respect, it is easier to get started using Python than to start using VB.NET, especially on non-Windows platforms.
I understand the popularity at the moment of the Python, however this language is also based on the C language. When it comes to more complex constructs Python cannot do them and I would be forced to rely on C.
It's pretty obvious that this guy hasn't done his research. This is a very ignorant statement about both Python and C in general.
I'd love to see *any* "complex construct" that C can do, that Python cannot do in a general computer science/algorithm sense.
One of the updates that folks seem to have overlooked is Metal, Apple's upcoming replacement for OpenGL.
While I think Apple is likely to continue supporting OpenGL for the foreseeable future, it's somewhat worrying that they've decided to just build a brand-new graphics library. It represents a refocusing of their optimization efforts, certainly, so in the future I would expect devs to have to use Metal in order to obtain decent graphics performance. This in turn will make development even harder, especially for cross-platform shops which expect OpenGL to work reasonably well in all environments...
Defaults should be sane, and optimized for the common case. Fall-through-by-default is not the common case, it's the exceptional case. Because C chose fall-through-by-default, programmers are penalized for the much more common case of no-fall-through by having to type "break;" at the end of every frickin' case statement.
Because of this, common C practice is to annotate intentional fall-through statements with a comment, like so:
switch(expr) {
case superset: /* superset code...*/ /* FALLTHROUGH */
case base: /* base code...*/ }
So, guess what Swift does? That's right, an explicitfallthrough keyword, which you can apply to get the uncommon (but, as you noted, occasionally useful) fallthrough behaviour. This is both wonderfully self-documenting, and eliminates the need for break in the common case. Switch statements in Swift are shorter and safer as a result. (Also, their use of Lisp/Scheme/...-esque matching semantics for switch is a nice touch, as are the genericized Enums...but that's a story for later).
Any C library can touch Python objects any time it likes, by nature of being linked to the Python C-API. However, you can only safely access Python objects while holding the GIL. CPython libraries are entered into with the GIL held (otherwise you couldn't even interact with the arguments given to the function), and they may decide to release the GIL some time later (and promise not to touch the Python API while the GIL is not held).
*Many* CPython release the GIL during operations that may be long-running, so you get the illusion that basically any long-running C operation releases the GIL.
PIL not releasing the GIL should be construed a bug in this case.
If you're feeling *particularly* devious, you can use a little-known Python feature called "for-else" (also "while-else") which allows you to tag "else" clauses onto for loops. Such a clause executes only if the loop runs to completion 'naturally' (i.e. if no break or exception happens within the loop block).
As a relatively obscure language feature, using it might make your code harder to read. It can help make a multilevel break (chained "else: continue; break" snippets at the end of loops), and reduces the number of flag tests and sentinels you need to do (e.g. a linear search, wherein the "else" case simply contains the if-not-found logic).
There are other alternatives to multi-level break: exceptions can break out of any number of loops until they reach an appropriate handler block, and function returns can always break out of any loop up to the top of the function.
As for switch/case: In C, they were basically a thin wrapper around jump tables for most switches (e.g. enums, small integers, duff's device, etc.). Python's preferred alternatives are key-value dictionaries (hashtables) or if/elif cascades. The former is very easy to setup and manipulate in Python (e.g. {1: 'spam', 2: 'eggs', 3: 'ham'}), unlike in C or C++. The latter is far more flexible than switch/case (e.g. being able to test ranges of values with "A <= x <= B" queries, test for multiple values with "x in (A, B, C)", or do arbitrary tests like "x.isspace()"), while avoiding the complexity of an entirely new language construct.
Finally, goto exists in Python as a third-party module. Go ahead, try it: it really works!
This implementation is not infeasible even when the players run in separate processes. I can observe your rand() state through the moves you make, and provided the remainder of the argument is the same (seeded with system time at the start of the match, simple RNG processing to derive a move), I can simply play randomly for the first 30 rounds (3^30 > 2^32) and observe your state. If I can come up with a set of RNG parameters (time-based seed, rand algorithm, sequence offset, processing strategy) that outputs your move sequence, then I can still beat your bot with a slightly worse win record. It takes 30 times more computational power, so about 180000 possibilities, but it's still tractable.
Suck is relative. I was implying they sucked according to GP's definition, which was that a "good" algorithm would require lots of data & computation time to beat. I would agree that they don't suck for their intended purpose (simple, fast, reasonably random, repeatable numbers). However, rand() does get (mis)used in a lot of contexts (especially security-conscious ones, or applications vulnerable to algorithmic complexity attacks) where it should not be used.
I should mention, though, that even in cases where it "shouldn't" matter, a weak rand() enables attacks on systems that should otherwise behave randomly. For example, many games (as you mention) use very simple implementations of rand(); such simple implementations also allow particularly hard-core gamers to abuse the system and earn much higher rewards (stat boosts, attack rolls, random encounters, etc.) than they ought to. Heck, there's an entire subcommunity of Pokémon game players dedicated to beating the game (and/or outperforming their peers) through methodical, systematic RNG abuse.
0) I have source code for my bot, the tourney announcement, and the tourney results. If you are really curious, ping me at my email address.
1) I never said you were *playing* a random opponent. Against an *arbitrary* opponent your optimal strategy is to play randomly. Any other strategy that you play can be exploited to your loss. In this way, random really is the game-theoretic optimal strategy. It's not just a buzzword.
2) Of course. I'm exploiting an implementation detail. This is a classic side-channel attack on an otherwise secure system.
3) Yes. I looked up the source code for libc implementations online. It's easy: google ' rand.c'. Examples: http://fxr.watson.org/fxr/source/stdlib/rand.c?v=FREEBSD-LIBC, http://fossies.org/dox/glibc-2.15/random_8c_source.html. I also got Microsoft's rand() implementation for their MSVC runtime because the source code for that comes with Visual Studio. Yes, I was using Windows. Contest submissions had to be in C or C++, and most programmers would rather use rand() (portable, simple, easy) than implement their own random() function or use the less-portable/dev/[u]random.
4) Contest programs ran in the same process, so your rand() state was shared. srand was forbidden, but we were given the tournament engine source code and so we knew when srand() was called and with what arguments (time(NULL)). To be specific: I pulled a single rand() value, then ran all my implementations of rand() with different seeds in the neighbourhood of time(NULL), and ran them for a variable number of iterations (up to 20, I think) to guess the sequence offset. The processing strategy was simply observing what values they were adding to the rand() value before taking it mod 3. The input is about 20 seconds * 5 libcs * 20 sequence offsets * 3 "processing strategies" = 6000 possibilities. Four dimensions, but they can all be constrained to small values.
I took first place in the full round-robin. The second part of the contest was a knockout tournament, and I wasn't using the kind of super-sophisticated modelling that my opponents used since the RNG breaker was already a fair amount of work. Consequently, at best I tied strong opponents, and lost on time.
Yes indeed, neonbot was my entry. Quite a remarkable small world. The contest was in 2007 (my first year of undergrad), and it was probably my favorite event of the year. Thanks for judging!
I'd think that unless you were playing a very large number of rounds such that you could infer the opponent's PRNG function and seed, or unless the opponent PRNG was REALLY bad, this would not work.
Actually, supposing the seed state is 32 bits in size, it really doesn't take that many rounds. Each round, one of three outcomes is produced. This yields roughly 1.6 bits of information about the generator's internal state. After 20 rounds, you have, in theory, enough information to infer the PRNG seed. If you can predict the opponent's move for 30 straight rounds, you can be pretty confident that you've determined both the seed and the function precisely. This works for arbitrary seeds.
Maybe if the seed were the time to the nearest hour you might be OK. However, if it used time to a millisecond then you'd have almost no chance of success. Any decent PRNG will show what would appear to be completely different behavior with even a slightly different seed.
With regards to the timestamp: srand(time(NULL)) isn't a random seed. If you can guess when the process called this function (hint: it's at least after the process was started!), you can then bruteforce over a very small number of possibilities. If the process was started, say, at 7:00pm for the contest start, and you run at 8:30pm, you've got a search space of just 5000000 milliseconds, which is trivial. My implementation worked for this contest (as evidenced by its extremely high win rate against rand()-using bots).
Now, if the PRNG were really lousy maybe you'd have a shot. It just seems unlikely that such a function would exist in any well-used library since the 60s. Sure, lots of functions are inadequate for cryptography, but even defeating these poor algorithms usually requires lots of data collection and a huge search. A PRNG that takes 5 years of supercomputer time would be considered broken, since a brute force keysearch might require the age of the universe. That doesn't mean that you're going to defeat it with a few rounds of RPS to figure out what it is doing.
This PRNG-breaking approach would work equally well for a crappy linear-congruential generator as for a modern Mersenne Twister, since it relies only on being able to guess the seed (not the entire internal state).
Most libc implementations of rand() really suck. They were originally implemented for memory economy and speed, and there was no concern about security. Now, such implementations are largely retained for compatibility, so that older programs can still produce the same results using fixed seeds. The various libcs are, arguably, the most-used libraries in existence. To beat many of these generators requires just one (or two) observations of the full 32-bit output, plus a trivial amount of computation.
Maybe about 10% or so. The contest was five years ago, so some of the details are a bit fuzzy. I don't believe we ever got the source code for other competitors, either, so I wouldn't know if they were using an RNG strategy or just a simple predictable one.
Evolution doesn't need to "progress" quickly. It has no defined end-goal, only the continued adaptation of species. Life adapts to its environment, whether the environment is an asteroid crater or an industrial park.
Evolution doesn't have to be "induced" by any great event. Catastrophic events are just one way in which evolution can operate, since they produce ecological voids which are rapidly filled by new (adapted) flora and fauna. Regular adaptation to ever-changing natural (and artificial) environments also drives evolution.
I once participated in a Rock-Paper-Scissors tournament put on by Epson (see, for example, http://www.campuslogix.com/rps_challenge/rps_challenge.html). They basically said "write a bot that will play RPS". Of course, the game-theoretic optimal strategy in such a contest is to just play randomly. You can beat the (Epson-supplied) rockbots and rotatebots easily, so with a bit of work you can do slightly above average.
Seeking a greater advantage, though, I coded my bot to also include a set of predictors for the random number generators for several popular libcs (as I did not which OS or distro the tournament machine would use). During a round, I would guess the random seed (current system time +/- a few seconds), the sequence offset, RNG processing strategy, and the algorithm used, and simply run a parallel copy of the libc RNG used by my opponent.
I was therefore able to beat most RNG-using opponents 9998/10000 times easily, a finding which rather surprised the judges:) I didn't win top prize (algorithm wasn't fast enough, and it turns out that was weighted more heavily than I expected), but I did get a high ranking and a cash prize.
Goes to show: sometimes a bit of "cheating" works well.
They've (either purposefully or inadvertently) created for themselves a bit of an AI challenge. If the hackers take this seriously enough, we could see the development of some pretty advanced game-specific AIs.
And, just like Australia, they might all eventually come to be accepted as mostly-normal members of society.
Slashdot Mirror
The headline on Slashdot is misleading - as the snippet says, locking and unlocking the device will restore the touchscreen. My guess (having worked on capacitive touch systems) is that the touchscreen doesn't properly recalibrate on a sudden temperature change, resulting in loss of touch detection until the touchscreen recalibrates (which happens every time you unlock the phone). This is easily fixed by a software or firmware change, and has a fairly simple workaround in the meantime.
Unlike what most commenters seem to assume, the phone is not suddenly unusable in the cold - just click the power button to lock the phone and click it again to unlock. Takes less than 2 seconds, after which you can go back to scrolling Facebook in the bitter cold.
If anyone's curious, I've dropped the decrypted contents of the "free sample" up on GitHub: https://github.com/nneonneo/eq.... Hopefully this makes analyzing the collection a bit easier. The code's pretty old - 2010-2013 according to timestamps - but it does look like real exploit/implant code from a distance.
Yes, and it's a fair point that most SSDs haven't been around long enough to even measure their long-term stability. SSD technology has also advanced very far in a short period of time - older generation SSDs are probably also much less mature in technology and therefore more prone to failure.
The SSD manufacturers have yet to see all the ways in which their drives can fail under real-world, long term conditions. I expect long term reliability to improve as companies develop a fuller understanding of the failure modes and countermeasures. For example, hard drives added shock (acceleration) sensors after laptops became commonplace - the failures caused by dropping the hard drive were not previously considered a major risk.
Let's work it out. A few years ago, TechReport ran an SSD endurance experiment to figure out how much punishment current-gen SSDs could take before failing. Their test setup essentially involved writing random data at maximum speed for 18 months straight. The results indicated that the worst SSD in their bunch, a Intel's 335 Series, wrote about 700 TB before dying, and the best SSD, a Samsung 840 Pro SSD, went on to 2.4 PB.
Various estimates say you can put between 60-75 hours of HD content on a 500GB drive, so, assuming the largest possible size, that works out to about 8.3 GB/hour. Since you're writing two streams, that's 16.6 GB/hour, or 145 TB per year. For the worst drive in the bunch, that's about 4.8 years of service (right at the upper end of your HDD's service life); for the best drive, it's over 16 years.
Keep in mind that these tests were all run on 250GB drives. Smaller drives have less flash to work with, and have to write over the same flash cells more often. Therefore, if you bought a 1TB drive, you can expect the lifetime to be easily 4x better (more if you're using a more recent drive, such as the Samsung 850 Pro) - 64 years of DVR recording should be more than sufficient.
If it really is only $75-120K to crack SHA1, I propose we start a Kickstarter to gather the funds. Given the estimate of a few months, we'll ship our SHA1 collision well before a lot of other Kickstarter projects ship their products :)
Manual car sensors can also be hacked! Shining bright lights at the windshield, especially in nighttime driving conditions, incapacitates the optical sensor of a manually-driven car. Worse, unlike self-driving cars, manual cars behave erratically or unpredictably in these conditions. Even worse, all cars are equipped with hardware that can generate these bright lights, meaning that any car can attack any other manual car in vision range.
Cars are doomed!
Some folks were asking how this works, so here goes:
newgrp is a UNIX utility that executes a shell with a new group ID (UNIX specification page: http://pubs.opengroup.org/onli...). This requires root permission since it can change the group ID to one outside the current shell's group list (e.g. to any group in the uid's group list). Therefore, newgrp is a setuid root application which launches a shell.
DYLD_PRINT_TO_FILE is a dyld (OS X dynamic linker) environment variable that tells dyld where to print debugging information. Ordinarily, dyld supports a large number of debugging options to facilitate debugging shared libraries and to allow neat tricks like DYLD_INSERT_LIBRARIES (equivalent to LD_PRELOAD on Linux). When dyld sees this environment variable, it opens a new file descriptor connected to the specified file. Since fds 0,1,2 are already connected to stdin, stdout and stderr, the file is opened as fd 3.
Notably, since newgrp starts as root, the file is opened using root's permissions, even though newgrp later drops privileges to spawn the shell.
Because DYLD_ environment variables can modify a program's behaviour in unexpected ways, they are usually deleted or sanitized prior to running setuid programs (because otherwise an unprivileged attacker could cause a setuid program to misbehave, exactly as in this exploit). Apple clearly forgot to sanitize the new DYLD_PRINT_TO_FILE when shipping Yosemite, opening this particular flaw up.
Finally, the (outer) echo command tells the subshell spawned by newgrp to execute the (inner) echo command, which outputs the string "$(whoami) ALL=(ALL) NOPASSWD:ALL" into fd 3, which (due to the DYLD_PRINT_TO_FILE variable) is /etc/sudoers. This line tells sudo that *any* account is allowed sudo access, and that no password is required to use sudo.
The subshell then exits (no more commands to run), and the final command "sudo -s" executes. Since sudo no longer requires a password, and all accounts can use sudo, "sudo -s" just immediately opens a root shell without prompting.
Efficiency needs to count programmer time, too. From watching first-year programmers in University struggle with C, to watching seasoned programmers struggle with C, I can assure you that Python wins on programmer efficiency. I've used C longer than I've used Python (~16 years for C, ~13 years for Python), so I am definitely comfortable with both, but I now use Python for virtually all general-purpose programming.
Even when CPU cycles count, I will usually prototype in Python to get all the algorithmic details right before porting to C. Often I won't even port the whole program; a number of my recent projects have had C routines called from Python front-end code (so that the front-end can handle stuff like HTTP requests, text parsing, response formatting and the like).
Finally, libraries like NumPy and Sage are taking Python beyond mere scripting and into the realm of serious scientific programming. It is now possible to write and use complex computer vision algorithms, mathematical algorithms, and heavy-duty number crunching (like MATLAB) in Python, meaning that a good amount of scientific computing is starting to be done with Python instead of more traditional languages like Perl, MATLAB or Java.
Your vbnc was last updated in 2010, and targets Visual Basic .NET 8, which was released with Visual Studio 2005. The VBNC compiler has not had any significant updates since 2011.
Visual Basic .NET is now on version 12. vbnc is horribly behind, and it does not appear to be actively supported. If your instructor were to use any newer language features, such as lambdas, iterators or asynchronous programming, you would not be able to use VBNC to compile that code and would probably have to resort to using Windows somehow.
On the flipside, Python now comes standard with most Linux distributions, and is standard with Mac OS X. It's very simple to install on Windows and even comes with a bare-bones IDE for editing code. In every respect, it is easier to get started using Python than to start using VB .NET, especially on non-Windows platforms.
It's pretty obvious that this guy hasn't done his research. This is a very ignorant statement about both Python and C in general.
I'd love to see *any* "complex construct" that C can do, that Python cannot do in a general computer science/algorithm sense.
One of the updates that folks seem to have overlooked is Metal, Apple's upcoming replacement for OpenGL.
While I think Apple is likely to continue supporting OpenGL for the foreseeable future, it's somewhat worrying that they've decided to just build a brand-new graphics library. It represents a refocusing of their optimization efforts, certainly, so in the future I would expect devs to have to use Metal in order to obtain decent graphics performance. This in turn will make development even harder, especially for cross-platform shops which expect OpenGL to work reasonably well in all environments...
No, because version 10^100 comes after that, at the same time that Apple and Google merge.
Defaults should be sane, and optimized for the common case. Fall-through-by-default is not the common case, it's the exceptional case. Because C chose fall-through-by-default, programmers are penalized for the much more common case of no-fall-through by having to type "break;" at the end of every frickin' case statement.
Because of this, common C practice is to annotate intentional fall-through statements with a comment, like so:
switch(expr) {
/* superset code ...*/
/* FALLTHROUGH */
/* base code ...*/
case superset:
case base:
}
So, guess what Swift does? That's right, an explicit fallthrough keyword, which you can apply to get the uncommon (but, as you noted, occasionally useful) fallthrough behaviour. This is both wonderfully self-documenting, and eliminates the need for break in the common case. Switch statements in Swift are shorter and safer as a result. (Also, their use of Lisp/Scheme/...-esque matching semantics for switch is a nice touch, as are the genericized Enums...but that's a story for later).
Any C library can touch Python objects any time it likes, by nature of being linked to the Python C-API. However, you can only safely access Python objects while holding the GIL. CPython libraries are entered into with the GIL held (otherwise you couldn't even interact with the arguments given to the function), and they may decide to release the GIL some time later (and promise not to touch the Python API while the GIL is not held).
*Many* CPython release the GIL during operations that may be long-running, so you get the illusion that basically any long-running C operation releases the GIL.
PIL not releasing the GIL should be construed a bug in this case.
If you're feeling *particularly* devious, you can use a little-known Python feature called "for-else" (also "while-else") which allows you to tag "else" clauses onto for loops. Such a clause executes only if the loop runs to completion 'naturally' (i.e. if no break or exception happens within the loop block).
As a relatively obscure language feature, using it might make your code harder to read. It can help make a multilevel break (chained "else: continue; break" snippets at the end of loops), and reduces the number of flag tests and sentinels you need to do (e.g. a linear search, wherein the "else" case simply contains the if-not-found logic).
There are other alternatives to multi-level break: exceptions can break out of any number of loops until they reach an appropriate handler block, and function returns can always break out of any loop up to the top of the function.
As for switch/case: In C, they were basically a thin wrapper around jump tables for most switches (e.g. enums, small integers, duff's device, etc.). Python's preferred alternatives are key-value dictionaries (hashtables) or if/elif cascades. The former is very easy to setup and manipulate in Python (e.g. {1: 'spam', 2: 'eggs', 3: 'ham'}), unlike in C or C++. The latter is far more flexible than switch/case (e.g. being able to test ranges of values with "A <= x <= B" queries, test for multiple values with "x in (A, B, C)", or do arbitrary tests like "x.isspace()"), while avoiding the complexity of an entirely new language construct.
Finally, goto exists in Python as a third-party module. Go ahead, try it: it really works!
This implementation is not infeasible even when the players run in separate processes. I can observe your rand() state through the moves you make, and provided the remainder of the argument is the same (seeded with system time at the start of the match, simple RNG processing to derive a move), I can simply play randomly for the first 30 rounds (3^30 > 2^32) and observe your state. If I can come up with a set of RNG parameters (time-based seed, rand algorithm, sequence offset, processing strategy) that outputs your move sequence, then I can still beat your bot with a slightly worse win record. It takes 30 times more computational power, so about 180000 possibilities, but it's still tractable.
Suck is relative. I was implying they sucked according to GP's definition, which was that a "good" algorithm would require lots of data & computation time to beat. I would agree that they don't suck for their intended purpose (simple, fast, reasonably random, repeatable numbers). However, rand() does get (mis)used in a lot of contexts (especially security-conscious ones, or applications vulnerable to algorithmic complexity attacks) where it should not be used.
I should mention, though, that even in cases where it "shouldn't" matter, a weak rand() enables attacks on systems that should otherwise behave randomly. For example, many games (as you mention) use very simple implementations of rand(); such simple implementations also allow particularly hard-core gamers to abuse the system and earn much higher rewards (stat boosts, attack rolls, random encounters, etc.) than they ought to. Heck, there's an entire subcommunity of Pokémon game players dedicated to beating the game (and/or outperforming their peers) through methodical, systematic RNG abuse.
0) I have source code for my bot, the tourney announcement, and the tourney results. If you are really curious, ping me at my email address.
1) I never said you were *playing* a random opponent. Against an *arbitrary* opponent your optimal strategy is to play randomly. Any other strategy that you play can be exploited to your loss. In this way, random really is the game-theoretic optimal strategy. It's not just a buzzword.
2) Of course. I'm exploiting an implementation detail. This is a classic side-channel attack on an otherwise secure system.
3) Yes. I looked up the source code for libc implementations online. It's easy: google ' rand.c'. Examples: http://fxr.watson.org/fxr/source/stdlib/rand.c?v=FREEBSD-LIBC, http://fossies.org/dox/glibc-2.15/random_8c_source.html. I also got Microsoft's rand() implementation for their MSVC runtime because the source code for that comes with Visual Studio. Yes, I was using Windows. Contest submissions had to be in C or C++, and most programmers would rather use rand() (portable, simple, easy) than implement their own random() function or use the less-portable /dev/[u]random.
4) Contest programs ran in the same process, so your rand() state was shared. srand was forbidden, but we were given the tournament engine source code and so we knew when srand() was called and with what arguments (time(NULL)). To be specific: I pulled a single rand() value, then ran all my implementations of rand() with different seeds in the neighbourhood of time(NULL), and ran them for a variable number of iterations (up to 20, I think) to guess the sequence offset. The processing strategy was simply observing what values they were adding to the rand() value before taking it mod 3. The input is about 20 seconds * 5 libcs * 20 sequence offsets * 3 "processing strategies" = 6000 possibilities. Four dimensions, but they can all be constrained to small values.
I took first place in the full round-robin. The second part of the contest was a knockout tournament, and I wasn't using the kind of super-sophisticated modelling that my opponents used since the RNG breaker was already a fair amount of work. Consequently, at best I tied strong opponents, and lost on time.
Yes indeed, neonbot was my entry. Quite a remarkable small world. The contest was in 2007 (my first year of undergrad), and it was probably my favorite event of the year. Thanks for judging!
I'd think that unless you were playing a very large number of rounds such that you could infer the opponent's PRNG function and seed, or unless the opponent PRNG was REALLY bad, this would not work.
Actually, supposing the seed state is 32 bits in size, it really doesn't take that many rounds. Each round, one of three outcomes is produced. This yields roughly 1.6 bits of information about the generator's internal state. After 20 rounds, you have, in theory, enough information to infer the PRNG seed. If you can predict the opponent's move for 30 straight rounds, you can be pretty confident that you've determined both the seed and the function precisely. This works for arbitrary seeds.
Maybe if the seed were the time to the nearest hour you might be OK. However, if it used time to a millisecond then you'd have almost no chance of success. Any decent PRNG will show what would appear to be completely different behavior with even a slightly different seed.
With regards to the timestamp: srand(time(NULL)) isn't a random seed. If you can guess when the process called this function (hint: it's at least after the process was started!), you can then bruteforce over a very small number of possibilities. If the process was started, say, at 7:00pm for the contest start, and you run at 8:30pm, you've got a search space of just 5000000 milliseconds, which is trivial. My implementation worked for this contest (as evidenced by its extremely high win rate against rand()-using bots).
Now, if the PRNG were really lousy maybe you'd have a shot. It just seems unlikely that such a function would exist in any well-used library since the 60s. Sure, lots of functions are inadequate for cryptography, but even defeating these poor algorithms usually requires lots of data collection and a huge search. A PRNG that takes 5 years of supercomputer time would be considered broken, since a brute force keysearch might require the age of the universe. That doesn't mean that you're going to defeat it with a few rounds of RPS to figure out what it is doing.
This PRNG-breaking approach would work equally well for a crappy linear-congruential generator as for a modern Mersenne Twister, since it relies only on being able to guess the seed (not the entire internal state).
Most libc implementations of rand() really suck. They were originally implemented for memory economy and speed, and there was no concern about security. Now, such implementations are largely retained for compatibility, so that older programs can still produce the same results using fixed seeds. The various libcs are, arguably, the most-used libraries in existence. To beat many of these generators requires just one (or two) observations of the full 32-bit output, plus a trivial amount of computation.
Maybe about 10% or so. The contest was five years ago, so some of the details are a bit fuzzy. I don't believe we ever got the source code for other competitors, either, so I wouldn't know if they were using an RNG strategy or just a simple predictable one.
Evolution doesn't need to "progress" quickly. It has no defined end-goal, only the continued adaptation of species. Life adapts to its environment, whether the environment is an asteroid crater or an industrial park.
Evolution doesn't have to be "induced" by any great event. Catastrophic events are just one way in which evolution can operate, since they produce ecological voids which are rapidly filled by new (adapted) flora and fauna. Regular adaptation to ever-changing natural (and artificial) environments also drives evolution.
I once participated in a Rock-Paper-Scissors tournament put on by Epson (see, for example, http://www.campuslogix.com/rps_challenge/rps_challenge.html). They basically said "write a bot that will play RPS". Of course, the game-theoretic optimal strategy in such a contest is to just play randomly. You can beat the (Epson-supplied) rockbots and rotatebots easily, so with a bit of work you can do slightly above average.
Seeking a greater advantage, though, I coded my bot to also include a set of predictors for the random number generators for several popular libcs (as I did not which OS or distro the tournament machine would use). During a round, I would guess the random seed (current system time +/- a few seconds), the sequence offset, RNG processing strategy, and the algorithm used, and simply run a parallel copy of the libc RNG used by my opponent.
I was therefore able to beat most RNG-using opponents 9998/10000 times easily, a finding which rather surprised the judges :) I didn't win top prize (algorithm wasn't fast enough, and it turns out that was weighted more heavily than I expected), but I did get a high ranking and a cash prize.
Goes to show: sometimes a bit of "cheating" works well.
They've (either purposefully or inadvertently) created for themselves a bit of an AI challenge. If the hackers take this seriously enough, we could see the development of some pretty advanced game-specific AIs.
And, just like Australia, they might all eventually come to be accepted as mostly-normal members of society.