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]
Usborne's 1983 classic Introduction to Machine Code for Beginners is an astounding book, written, designed and illustrated by Naomi Reed, Graham Round and Lynne Norman. It uses beautiful infographics and clear writing to provide an introduction to 6502 and Z80 assembler, and it's no wonder that used copies go for as much as $600. I was reminded of it this morning when @amanicdroid tweeted me with a link to a PDF of the book's interior. I'd love to see this book updated for modern computers and reprinted.
Alex sez, "Algoraves are parties where people come together to dance to algorithms. It generally involves some live coding but any producers making music "wholly or predominantly characterised by the emission of a succession of repetitive conditionals' are welcome. Generally some aspect of the algorithmic processes are visible, but the focus is actually on the audience, and having serious fun.
We've had a few parties across the UK and Germany, and are spreading further afield in Mexico and Australia. The concept is still developing though, and is being defined by whoever turns up."
Here's the video of "It's not a fax machine connected to a waffle iron," the talk I gave at the Re:publica conference in Berlin this week: "Lawmakers treat the Internet like it's Telephone 2.0, the Second Coming of Video on Demand, or the World's Number One Porn Distribution Service, but it's really the nervous system of the 21st Century. Unless we stop the trend toward depraved indifference in Internet law, making – and freedom – will die."
re:publica 2013 - Cory Doctorow: It's not a fax machine connected to a waffle iron
The MIT Media Lab's Lifelong Kindergarten Group has shipped version 2.0 of Scratch, the justly famed and much-loved programming language for kids. Scratch makes it easy to create powerful simulations and games, even for small kids (basically, if you can read, you're ready for Scratch). The new version of Scratch runs right in a browser (no downloads or installs required), and is remarkable in its polish and power to excite. The programming environment is embedded in a sharing and shareable community, with millions of Scratch projects ready to be downloaded and remixed. It's just amazing
With Scratch, you can program your own interactive stories, games, and animations — and share your creations with others in the online community.
Scratch helps young people learn to think creatively, reason systematically, and work collaboratively — essential skills for life in the 21st century.
Share with others around the world
(via O'Reilly Radar)
Wagner James Au sez, "OpenWorm, as the name suggests, is a collaborative open source project to computationally create a simple artificial life form -- an earth worm -- from the cellular level to a point where it's sophisticated enough to solve basic problems. They're still in early stages, with the latest demo, a developer on the project tells me, being 'a particle simulation of five connected muscle segments moving together through a body of water.'"
An Open Source Artificial Life Project Called OpenWorm
Given a standard Tetris engine (which drops pieces in a pseudorandom order, has previews, and allows holding), this method will allow you to play Tetris forever. As always, the most fascinating thing about this is the specialized vocabulary used to describe the method:
Worst case bag distributions such as H?XX?X? and H?XXX?? deserve a special mention. The first piece 'H' denotes a piece which must be placed in Hold in order to follow the STZ loop procedure. Pieces from the LJO loop are denoted by '?', and the remaining pieces are denoted by 'X'. Using 3 previews and Hold, it is only possible to see the first 4 pieces of the bag before the second piece enters the screen. This means you only see H?XX, and only know the first piece of the LJO loop. Because H must be put in Hold, you are forced to make a decision without knowing the order of the rest of the LJO loop. If the O comes first, you can follow the procedure above without problems. The rest of the time you will run into complications like this:
(via Hacker News)