|
an idea i had a while back but forgot about until earlier today was trying to use physical processes to solve math/software problems. the specific idea i had was to use electricity's property of always finding "the path of least resistance" to solve a graph-search problem.
if you can represent a search graph using a bunch of resistors, then theoretically, you could plug in your resistor network and let the electric current find the solution for you. since it checks all paths in parallel, it would work in pretty much constant time. the problem with it is that it would only be faster than a software search algorithm for a large enough graph, and for graphs of that size building the resistor network becomes non-trivial. if it were possible to turn this into a more general massively parallel computer of some sort, it might be worth it, but it seems unlikely.
another related thing that came up was using physical processes to generate one-way functions in math. so, for example, if you were given the description of a container and a ball within the container, along with the initial position and velocity of the ball, you could use the laws of physics to figure out where the ball ends up. however, given the description of the container and the final position of the ball, it's practically impossible (i think) to figure out the initial position and velocity of the ball. in this case, it turns out to be very similar to a hash function, since the input space of the function (ball position and velocity) is much larger than the output space (ball position), and multiple inputs can map to the same output. so in fact it's actually impossible to reverse the function.
there's probably some other physical process out there that's a better candidate..
[ 12 Comments... ]
much snow is falling. that is all. :)
[ 15 Comments... ]
so one of the things that falls under the "slightly better design" in my previous rant is stricter typing. most of the input validation i had to do was on a namespace variable that would get passed in to a class' constructor, and would be used to load appropriate config data from a config file. the namespace would be a String, but I'd always have to check it to make sure it wasn't null or empty (only whitespace). this could have been made unnecessary by having a Namespace object that just wrapped a String and did the checking in one spot.
taking this further, it's probably possible to replace most of the primitive variables that get passed around with more typesafe wrapper classes that not only do error-checking and input validation for you, but can also provide custom functionality. i guess that's kind of the point of object-oriented programming, but in order to take it to the level i'm thinking of, it would have to be supported by the platform from the ground up. everything from the UI down to the innards of the system code would have to use stricter types, rather than using ints and chars and constantly checking them for validity.
so, for example, let's assume we wanted to get a port number for some TCP connection we wanted to make. instead of using an int, we'd use a special PortNumber class that wrapped an int, and it would restrict the value of the int to a valid port number [1025, 65535]. there would be a custom renderer that would draw the UI element for a PortNumber, such that the user wouldn't be able to enter a value outside the range. the actual renderer could be done using a text field, or a number spinner, or whatever, but it wouldn't accept anything except a valid port number. the PortNumber object would be passed around all the way down to the network stack, which would serialize it directly into the TCP packets that get written out. once created, the PortNumber object would never have to be checked for validity, saving a lot of checks along the way at the expense of slightly less efficient (yet more modular) code.
a lot of the variables being passed around in most code have semantic information beyond the syntactic type that they're represented by. the more of this semantic information that can be captured by the type, the more checks you can do at compile-time, and the easier it is to debug. this is kind of the point of hungarian notation, but getting at it in a different way.
[ 0 Comments... ]
doesn't this qualify as a pyramid scheme? it seems to be based on the same principles, at least. you'll get twice your money back, as long as there are two bigger fools than you. at some point, it's going to be just too expensive to buy an ad, so the fools are going to run out, and you get screwed. on the other hand, the guy who came up with it seems to have netted a decent profit.
[ 6 Comments... ]
last thursday, i decided to try out one of topcoder's development contests. (i'm not sure how many of these links you'll be able to access unless you're logged in to topcoder, but i'll keep linking anyway). the contests are posted every thursday, and submissions are due the next thursday, hence my non-posting for the last week.
i spent pretty much all my spare time for the last week working on the Sliding Tile Puzzle 1.0 component. it took me only a couple of days to get to being functionally complete; the rest of the time was spent productizing it to the standard that they require. even so, i don't think my final submission will pass their screening. the overhead that goes with the code is just too high.
documentation was a big sticking point. i hate documenting my code - more so than other people, i think. in the actual production code files (i.e. not including unit test files), there were 3570 lines; 1873 of these lines were javadoc, and an additional 407 were blank. that leaves only 1290 lines of actual code. i would guesstimate that around 20% of that was just error-checking and input validation, a lot of which would have been unnecessary with a slightly better design. the unit test files were another 1695 lines in all.
i understand most of this stuff is actually useful to them, since it's almost guaranteed that the same developer will never come back to make revisions to the code, so they need it to be properly documented and have a regression test suite. but it's still a pain in the ass.
there were other things that annoyed me, and that i think are preventable. the design documentation comes in a poseidon zuml file, and (almost always, according to the forums) generates incorrect stubs. it took me a while to get the stubs working, and i had to basically go over every public class, method, and variable and make sure it was generated properly.
bad class/variable names was another big problem; i've griped about this before. they don't use hungarian notation, but their variable names were just as fugly. if all the code is in located in the com.topcoder.util.puzzle.slidingtile package, is it really necessary to prepend "SlidingTilePuzzle" to the beginning of each class name? it's kind of redundant, specially when the style guidelines disallow block imports; you have to import each class individually, so it's pretty clear where they're coming from.
the long class/variable names had a cascading effect with the 120 characters-per-line limit and javadoc - the line limit caused the code to wrap a lot, and combined with the javadoc, made everything very vertically spaced out. i think this is the first time in my life i've dealt with code that actually *requires* dual 21-inch LCD flat panels à la googleplex to be nicely viewable. i hate it when functions are longer than a screenful, since it becomes exponentially harder to grasp when you have to constantly page up/down to see the whole thing.
as you might have guessed, i also have issues with their style guide. for the most part it follows sun's java coding conventions, so it's not too bad. the bad part is how they enforce it. there's a program called checkstyle that you can run that will spit out a list of all the style errors. it takes a configuration file, and topcoder provides this on their website. there's another program called jalopy that will try and reformat your code. it also takes a configuration file, and topcoder also provides this on their website. you'd think that if you ran jalopy on your code, it would reformat your code in accordance with their style guidelines, and checkstyle wouldn't complain. you'd think.
on top of everything, my internet died yesterday, so i had to grab the midnight bus to the university to submit the code. i ended up fixing more style issues while wireless-ing in the CPH foyer, finally giving up at 3am with over 100 style warnings, and just submitted what i had. the sample review scorecard doesn't give style too much weight, but it does seem kind of strict in the wording, specially given their tools don't work as advertised.
wow, that was a long rant. but as further justification that this is a systemic problem, and not just me whining about things, only 5 of the 22 registered competitors actually submitted anything at all.
[ 4 Comments... ]
it seems pretty obvious to me that the whole password model of authenticating people is broken. first there were just usernames, which also served as passwords. then there were usernames AND passwords. then they added security questions to which you had to give the right answer. now some sites even have user-provided security questions, so you have to give your question and your answer. all they're doing is increasing the number of things the user has to provide, which is effectively the same as bumping up the minimum password length. (i.e. if you concatenated your username, password, security question, and security answer, that would be your new password). it's stupid. passwords can be broken by any number of techniques, from a simple brute-force search to dumpster diving to social engineering. i could go on for a while describing how the password model is broken, but you probably already know that.
next up is two-factor authentication. you need to provide something you have and something you know. usually this involves a password, combined with some sort of biometric dealie, whether it's a fingerprint, retinal scan, voiceprint, or even keystroke pattern recognition. this is better, but it really shouldn't be called two-factor authentication because the password half of it is still broken. it's basically just a biometric authentication. this is (as of now) stronger, and the people selling these solutions would have you believe that they are nigh-unbreakable. don't believe everything you hear. eventually this will be broken too. it's possible for attackers to get your fingerprint from anything you touch, or get your voiceprint from a recording. retinal scan might be harder, but hey, they did it entrapment, so it can't be that hard. eventually anything that just captures some physical characteristic will also be as broken as passwords are today. even RFID implants suffer from the same problem as biometric: the response from an RFID tag can be recorded and replayed (assuming my understanding of how they work is correct - I could be wrong on this one).
one thing all of the above methods have in common is that they're not dynamic or interactive. each of these basically prompts you exactly once for something (either a password, fingerprint, ...) and if you provide it successfully, you're good to go. this means that any sort of man-in-the-middle attack (which is effectively what's happening when you steal someone's fingerprint) can break it. what we need is an authentication method that changes every time it's used. something that's interactive, something that requires a "conversation" between the authenticator and authenticatee rather than just a one-time exchange, has the ability to be dynamic in such a way. the first step in the conversation could be the same (providing a username or some pointer to the identity you wish to authenticate against), but the rest of the conversation should change.
i don't have any specific ideas on how to actually make the conversation change such that the authenticatee can provide the correct responses to the authenticator without having any previously-agreed upon passwords/keys, but there must be some way to do it. ideas?
[ 4 Comments... ]
so this site has been switched over to the OpenID login i described earlier. you don't need to log in again or restart your computers or anything stupid like that; changes should be transparent. instead of the old username/password login in the navbar, there is now an OpenID identity URL-based login. if you enter an OpenID and you don't have an account, one will be automatically created. the account page has been updated so you can edit your handle/email if you want to.
as always, contact me if you run into any problems.
[ 0 Comments... ]
i was spelunking through some open source project the other day, and it really bugged me that the code not only used bad (i.e. systems) hungarian notation, but had variable names that were very similar to each other. so there were a whole bunch of variables with messy and meaningless prefixes, and then differed by only a letter or two. this made it really hard to read, because when you're comparing two long strings, you don't actually compare every single character. so i would be looking at the code and mis-read one variable as another and confuse the heck out of myself.
so, when y'alls are writing code, do yourself and others a favor: in addition to naming your variables meaningfully, make sure that variables that are used in proximity to each other have some minimum hamming distance between their names. this prevents both mis-typing and mis-reading the code, and will help make the world a better place. (also, if you must use hungarian notation, try to use apps hungarian. but really, read this and figure out your own notation that is appropriate to the code you're writing.)
[ 0 Comments... ]
today's big news is project blackbox. man, do i want one of those! watch the video, it's kind of cool. as noted in the slashdot post, something like this was predicted by cringely almost a year ago, except it was google, not sun. interesting.
this reminds me of T.E.U., a story i read a while ago, wherein a guy lives in one of those containers and gets shipped around from place to place to wherever his services are needed. it's pretty cool. i love the part about the bagel (even if you don't read the whole thing, ctrl-f for "bagel" and read that paragraph).
[ 3 Comments... ]
i was reading this article, and although it doesn't really go into any sort of detail about what exactly the information server does, the general concept does seem pretty cool, and something that i think will be useful in the near future. one of the main causes of information overload is not having the information in right format to be dealt with easily. too often the information we get is unstructured and needs to be reformatted before it becomes usable. a trivial example that we've all probably dealt with is getting appointment information in an email (instead of some sort of generic calendar entry object that can be tossed directly into a calendar or to an alarm clock).
some sort of server that processes information and makes it more usable sounds like one of those things that would be infinitely more useful than it seems to at first (i.e. more uses for it crawl out of the woodwork once it has been developed). i'm not sure if this is what the IBM server does, but it would be cool if it did.
[ 0 Comments... ]
|