Felienne describes how she, Daan van Berkel and some other friends went away for a weekend to hack a Turing machine out of Excel formulas. Lacking an infinitely long tape, they had to kludge around a bit, but the outcome is both cool and instructional (here's the machine itself). The Turing Machine is Alan Turing's "hypothetical device that manipulates symbols on a strip of tape," which formed the basis for modern, general-purpose computers.
Read the rest
Georg sez, "End to end cryptography is one of the few truly effective ways in which privacy and security can be protected. GnuPG is the central tool for this, recommended and used by security icons such as Bruce Schneier. While the software itself is easier to use than most people realize, key exchange is cumbersome. The authors of GnuPG have developed a concept that will solve this issue: STEED. So this is a call to action for tomorrow's Software Freedom Day. Help spread the word so one of the biggest obstacles to pervasive end to end cryptography will be solved for good. Let the STEED run!"
Read the rest
Ben West read my novel Little Brother in tandem with the Edward Snowden leaks about NSA spying, and it got him thinking about a browser plugin called Paranoid Browsing to make it harder to profile your traffic based on surveillance. He's posted the source-code to GitHub and looking for critical feedback about the robustness of the system -- remember, the only experimental methodology for validating a security system is public discussion, because otherwise, you never know if your system is secure, or just secure against people who are stupider than you.
Read the rest
Unsupervised joke generation from big data [PDF], a paper by University of Edinburgh researchers Sasa Petrovic and David Matthews, describes an ingenious and successful method for teaching a computer to make up jokes like "I like my relationships like I like my source, open;" "I like my coffee like I like my war, cold;" and "I like my boys like I like my sectors, bad." The researchers wrote code that called on Google's n-gram database to find noun-attribute pairs, zero in on nouns with ambiguous meaning, and automatically generate jokes.
Read the rest
K2G2 -- a wiki for "krafty knerds and geek girls" -- has a marvellous series of posts about "Computational Craft" through which traditional crafting practices, like knitting, are analyzed through the lens of computer science. The most recent post, A Computational Model of Knitting, point out the amazing parallels between knitting and computing, with knitting needles performing stack and dequeue operations, "While straight needles with caps store and retrieve their stitches according to the principle of LIFO (first in - last out), double pointed and circular needles additionally implement the functions of a queue or FIFO (first in – first out), effectively forming a double ended queue, also known as dequeue."
Read the rest
In Xerox scanners/photocopiers randomly alter numbers in scanned documents, computer scientist David Kriesel shows that the Xerox WorkCentre 7535 randomly changes the numbers in its scans. The copier has firmware that tries to compress images by recognizing the numbers and letters in the documents it scans, and when it misinterprets those numbers, it produces untrustworthy output. The bug also occurs in the Xerox 7556 and possibly other machines, and as Kriesel points out, this could mean that engineering diagrams, invoices, prescriptions, architectural drawings and other documents whose numeric values are potentially a matter of life-and-death (or at least financial stability) are being randomly edited by machines we count on to produce faithful copies.
Read the rest
Dr. Joseph Bonneau, an engineer at Google, is the first-ever winner of the NSA's new Science of Security (SoS) Competition, a prize for excellence in cyber-security research. On learning that he had won the first prize, he published a scorching blog-post excoriating the NSA for its dragnet surveillance and opining "I don’t think a free society is compatible with an organisation like the NSA in its current form."
Read the rest
The US Patent and Trademark Office is required by law to let the public submit "prior art" for pending patents -- essentially, evidence that the thing the patent-filer is claiming to have invented already exists. People who spot patents in need of killing post them to a Stack Exchange forum called Ask Patents, in the hopes that other forum members will come up with invalidating art.
Joel Spolsky writes about how he found -- in 15 minutes, mind you -- the prior art necessary to invalidate a dumb-ass Microsoft patent on scaling images. He documents the process by which he did it, and shows how easily you could do it, too. As Spolsky points out, software patents are all basically shit, and trivial to prove as such. It just takes a dedicated army of freedom fighters to find and submit the prior art that helps the overworked patent examiners at the USPTO to reject the garbage they get by the truckload.
Software patent applications are of uniformly poor quality. They are remarkably easy to find prior art for. Ask Patents can be used to block them with very little work. And this kind of individual destruction of one software patent application at a time might start to make a dent in the mountain of bad patents getting granted.
My dream is that when big companies hear about how friggin’ easy it is to block a patent application, they’ll use Ask Patents to start messing with their competitors. How cool would it be if Apple, Samsung, Oracle and Google got into a Mexican Standoff on Ask Patents? If each of those companies had three or four engineers dedicating a few hours every day to picking off their competitors’ applications, the number of granted patents to those companies would grind to a halt. Wouldn’t that be something!
Victory Lap for Ask Patents - Joel on Software
(via O'Reilly Radar)
Fast, Accurate Detection of 100,000 Object Classes on a Single Machine a prizewinning paper by Google Research scientists, describes a breakthrough in machine vision that can distinguish between a huge class of objects 20,000 times faster than before.
This so-called convolution operator is one of the key operations used in computer vision and, more broadly, all of signal processing. Unfortunately, it is computationally expensive and hence researchers use it sparingly or employ exotic SIMD hardware like GPUs and FPGAs to mitigate the computational cost. We turn things on their head by showing how one can use fast table lookup — a method called hashing — to trade time for space, replacing the computationally-expensive inner loop of the convolution operator — a sequence of multiplications and additions — required for performing millions of convolutions with a single table lookup.
We demonstrate the advantages of our approach by scaling object detection from the current state of the art involving several hundred or at most a few thousand of object categories to 100,000 categories requiring what would amount to more than a million convolutions. Moreover, our demonstration was carried out on a single commodity computer requiring only a few seconds for each image. The basic technology is used in several pieces of Google infrastructure and can be applied to problems outside of computer vision such as auditory signal processing.
Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
(Image: Clutter, a Creative Commons Attribution Share-Alike (2.0) image from neofob's photostream)
My latest Locus column is Teaching Computers Shows Us How Little We Understand About Ourselves, an essay about how ideas we think of as simple and well-understood -- names, families, fairness in games -- turn out to be transcendentally complicated when we try to define them in rule-based terms for computers. I'm especially happy with how this came out.
Systems like Netflix and Amazon Kindle try to encode formal definitions of "family" based on assumptions about where you live -- someone is in your immediate family if you share a roof -- how you're genetically related -- someone is immediate family if you have a close blood-tie -- how you're legally related -- someone is in your family if the government recognizes your relationship -- or how many of you there are -- families have no more than X people in them. All of these limitations are materially incorrect in innumerable situations.
What's worse, by encoding errors about the true shape of family in software, companies and their programmers often further victimize the already-victimized -- for example, by not recognizing the familial relationship between people who have been separated by war, or people whose marriage is discriminated against by the state on the basis of religion or sexual orientation, or people whose families have been torn apart by violence.
The ambiguity that is inherent in our human lives continues to rub up against our computerized need for rigid categories in ways small and large. Facebook wants to collapse our relationships between one another according to categories that conform more closely to its corporate strategy than reality -- there's no way to define your relationship with your boss as "Not a friend, but I have to pretend he is."
Teaching Computers Shows Us How Little We Understand About Ourselves
He was one of the most influential, important and visionary
computer scientists of all time. He died peacefully at home
, in his sleep. Goodbye, Dr Englebart. Thank you for all you did.
I posted in 2011 about the Digi-Comp I, a 1963 mechanical digital computer made of polystyrene and used to teach the fundamentals of boolean logic, binary, and computer programming. I'd just discovered that Evil Mad Scientist Labs sells a wooden version of its successor, the Digi-Comp II, which uses a pachinko-style marble-run to do the same thing (the Evil version is CNC-milled and laser-cut). They call it a "Rolling-Ball Binary Digital Mechanical Computer." It is both beautiful and very clever indeed.
Overall, it is slightly smaller than the original (mid 1960′s) Digi-Comp II, which used half-inch diameter glass marbles. Rather than marbles, we’ve opted for pachinko balls, which are shiny steel balls 11 mm (about 7/16") in diameter. Using the smaller size has allowed us to reduce some of the feature sizes, and reduce the overall size of the machine from 14×28.5″ to 10×24", while retaining all of the original functions and remaining finger-friendly.
The Digi-Comp II: First Edition is CNC carved from rock-solid half-inch hardwood plywood, laser-engraved to provide it with labels, and hand fitted with over 60 laser-cut parts. It comes assembled, tested, and ready to use.
It sells for $279.
Digi-Comp II: First Edition
WiSee is a reasearch project at the University of Washington; as described in this paper, it uses standard WiFi hardware to sense the location and movements of people within range of the signal. Using machine-learning, it maps specific interference patterns to specific gestures, so that it knows that -- for example -- you're waving your hand in the air. This gesture-sensing can be used to control various devices in your home:
WiSee is a novel interaction interface that leverages ongoing wireless transmissions in the environment (e.g., WiFi) to enable whole-home sensing and recognition of human gestures. Since wireless signals do not require line-of-sight and can traverse through walls, WiSee can enable whole-home gesture recognition using few wireless sources (e.g., a Wi-Fi router and a few mobile devices in the living room).
WiSee is the first wireless system that can identify gestures in line-of-sight, non-line-of-sight, and through-the-wall scenarios. Unlike other gesture recognition systems like Kinect, Leap Motion or MYO, WiSee requires neither an infrastructure of cameras nor user instrumentation of devices. We implement a proof-of-concept prototype of WiSee and evaluate it in both an office environment and a two-bedroom apartment. Our results show that WiSee can identify and classify a set of nine gestures with an average accuracy of 94%...
WiSee takes advantage of the technology trend of MIMO, the fact that wireless devices today carry multiple antennas (which are primarily used to improve capacity). A WiSee/WiSee-enabled receiver would use these multiple antennas in a different way to focus only on the user in control, thus eliminating interference from other people.
Michael Birken lays out, in detail, a method for teaching a computer to draw arbitrary 8-bit images by playing Tetris, strategically deploying blocks of various colors to cause exactly the picture you want to emerge. The method is (as you'd imagine), starkly terrifying in its complexity, but the video speaks for itself.
The algorithm converts pixels from a source image into squares in the Tetris playfield, one row at a time from the bottom up. To generate an individual square, the algorithm assembles a structure consisting of a rectangular region fully supported by a single square protruding from the bottom. When the rectangular region is completed, its rows are cleared, leaving behind the protruding square. Three examples of the process appear below.
The algorithm can also generate multiple squares with a single structure as shown below.
During construction of a row, all of the squares produced by this method must be supported. In the images above, the generated squares are supported by the floor of the playfield. However, if an arbitrary row contains holes, it may not provide the support necessary for the construction of the row above it. The algorithm solves this problem by constructing a flat platform on top of the row with holes. In the animation below, a platform is built above a row comprising of a single red square. The platform is a temporary structure and inserting the final piece removes it.
Tetris Printer Algorithm
(via Hacker News)
Here's a 40-minute video in which Tom Stuart gives a talk summarizing one of the chapters from him new book Understanding Computation, describing the halting state problem and how it relates to bugs, Turing machines, Turing completeness, computability, malware checking for various mobile app stores, and related subjects. The Halting State problem -- which relates to the impossibility of knowing what a program will do with all possible inputs -- is one of the most important and hardest-to-understand ideas in computer science, and Stuart does a fantastic job with it here. You don't need to be a master programmer or a computer science buff to get it, and even if you only absorb 50 percent of it, it's so engagingly presented, and so blazingly relevant to life in the 21st century, that you won't regret it.
At Scottish Ruby Conference 2013 I gave a talk called Impossible Programs, adapted from chapter 8 of Understanding Computation. It’s a talk about programs that are impossible to write in Ruby — it covers undecidability, the halting problem and Rice’s theorem, explained in plain English and illustrated with Ruby code. The slides are available
Nate Anderson Dan Goodin follows up on Nate Anderson's excellent piece on the nuts and bolts of password cracking with a further attempt to decrypt an encrypted password file leaked from LivingSocial, this time with the aid of experts. The password file they were working on was encrypted with the relatively weak (and now deprecated) SHA1 hashing algorithm, and they were only attacking it with a single GPU on a commodity PC, and were able to extract over 90% of the passwords in the file.
The discussion of the guesswork and refinement techniques used in extracting passwords is absolutely fascinating and really is a must-read. However, the whole exercise is still a bit inconclusive -- in the end, we know that a badly encrypted password file is vulnerable to an underpowered password-cracking device. But what we need to know is whether a well-encrypted password file will stand up to a good password-cracking system.
The specific type of hybrid attack that cracked that password is known as a combinator attack. It combines each word in a dictionary with every other word in the dictionary. Because these attacks are capable of generating a huge number of guesses—the square of the number of words in the dict—crackers often work with smaller word lists or simply terminate a run in progress once things start slowing down. Other times, they combine words from one big dictionary with words from a smaller one. Steube was able to crack "momof3g8kids" because he had "momof3g" in his 111 million dict and "8kids" in a smaller dict...
What was remarkable about all three cracking sessions were the types of plains that got revealed. They included passcodes such as "k1araj0hns0n," "Sh1a-labe0uf," "Apr!l221973," "Qbesancon321," "DG091101%," "@Yourmom69," "ilovetofunot," "windermere2313," "tmdmmj17," and "BandGeek2014." Also included in the list: "all of the lights" (yes, spaces are allowed on many sites), "i hate hackers," "allineedislove," "ilovemySister31," "iloveyousomuch," "Philippians4:13," "Philippians4:6-7," and "qeadzcwrsfxv1331." "gonefishing1125" was another password Steube saw appear on his computer screen. Seconds after it was cracked, he noted, "You won't ever find it using brute force."
Anatomy of a hack: How crackers ransack passwords like “qeadzcwrsfxv1331”
Remember the gigantic data-center that the NSA is building in Utah in order to (illegally) process the electronic communications of the whole world? Turns out that the state of Utah plans on taxing the titanic amounts of electricity it will consume at 6%. The NSA is pissed.
"We are quite concerned [about] this," Harvey Davis, NSA director of installations and logistics, wrote in the April 26 email, obtained through a Utah open records law request.
In a follow-up email Davis sent 31 minutes later, he explained: "The long and short of it is: Long-term stability in the utility rates was a major factor in Utah being selected as our site for our $1.5 billion construction at Camp Williams. HB325 runs counter to what we expected."
HB325, which Herbert signed into law April 1, benefits the Utah Military Installation Development Authority (MIDA). It allows the entity, which was set up to put select military properties on the public tax rolls, to collect a tax of up to 6 percent on Rocky Mountain Power electricity used by the Utah Data Center.
In surprise to NSA, Utah Data Center may pay tax on electricity [Nate Carlisle/The Salt Lake Tribune]