Another possible solution to an NP-complete problem?

A couple of days ago a research team comprised of faculty at Nanyang Technological University in Singapore, the University of Southampton in the UK, and IQFR-CSIC in Madrid, Spain published a paper containing a creative solution to a problem known to be NP-complete, namely a version of the traveling salesman problem. The TSP, in summary, postulates a scenario in which you have an arbitrary number of towns spread over a large area and an arbitrary number of paths connecting them. What is the shortest possible path one can take in which the traveler visits each town only once and returns to the point of origin? The answer is not a simple one, and in scenarios larger than a couple of towns (or nodes in a graph) the number of possible combinations rapidly balloons out of control. There are different strategies for finding the optimal path; brute force (trying every possible path) is guaranteed to work but the amount of time required to do so makes it prohibitive past a trivial number of nodes. Try it with a modest sized graph of only twenty towns and you may as well give up unless you want to try a more arcane technique like the Held-Karp or branch-and-bound algorithms. There are techniques to solve the TSP but several of the most feasible are very processor intensive (one required a 110 system cluster, and all of them count their CPU time in the tens of years). So, hamiltonian network problems are nothing to sneeze at.

The research team set up a network of optical fibres and couplers several kilometers in size which represented a set of five towns and the roads connecting them. The length of each optical fibre was precisely calibrated to introduce a unique and measurable delay in the transmission of light through the network. You could think of it like numbering vertices in a graph to identify them. After assembly, the experiment consisted of transmitting pulses of light into the network of optical fibers. As photons are wont to do, when presented with a set of possible paths they follow all of them simultaneously and thus traversed every coupler in the network. Due to the fact that you can add up the delays incurred by each path through the network the researchers successfully predicted when the first pulse would exit the network of optical fibers, which proved by performance that the network was Hamiltonian in nature, and that the most optimal solution had been determined for it. In a cryptographic sense the experiment is an oracle - put a question in, get an answer out that you can then do something useful with (like verify it).

But... why do we care? What's so important about being able to find the shortest path through a network?

More under the cut...

The Doctor | 23 April 2014, 10:00 hours | default | No comments



Note: If the file is too large for your browser to render as a pop-up, right click on the above thumbnail and select "Open in new tab" or "Open in new window".

Song: Showtime: Imp Strife Mix by Malcolm Brown, George Buzinkai, and Curt Blakeslee
Album: Homestuck Volumes 1-4
Book: Overthrowing the Old Gods by Don Webb
License: CC BY-NC-SA v3.0

The Doctor | 20 April 2014, 16:53 hours | images | No comments

How to move your /boot partition onto removable media.

Part of every traveler's threat model today should include the following scenario:

When you're trying to fly into or out of an airport en route to someplace else, it is entirely possible that the airport's security staff will take you aside for a more thorough search and questioning while your stuff is taken someplace out of your control and analyzed. We know that there are malware packages available today that boobytrap the boot device of laptop computers to install various forms of surveillance malware which run the next time you start your machine up and compromise the OS even though you may have locked it down to prevent live attacks. That the malware may capture the passphrase used to unlock an encrypted hard drives in the computer is an additional kick in the pants that one must be prepared to dodge.

Here's one way to mitigate this threat, which involves the use of a USB key that you work to keep out of the clutches of others at all times.

More under the cut...

The Doctor | 19 April 2014, 19:29 hours | content | No comments

Mass producing custom stem cells and advances in desktop testing.

Let's cut through some FUD: Human stem cells are pretty easy to come by. Embryos have not been involved in the process for well over ten years that I can recall off the top of my head, and probably closer to twenty. Every human body has stockpiles of them that can be extracted with minor surgical procedures. The procedures in question usually involves scarily long needles that reach deeply enough inside the body to extract them, which might be why research into re-embryonization of other kinds of cells has proceeded at a good clip. To summarize, medical science has been discovering and perfecting ways of turning cells of different kinds (like skin cells) back into stem cells, whereupon they can be coaxed into differentiating into other kinds of cells. Recently, scientists at the Institute of Molecular and Cell Biology at A*STAR have developed a method of de-differentiating blood cells back into puripotent stem cells which can then be caused to replicate and eventually turn into just about any other kind of cell a body is capable of incorporating. Most interesting is that they only need a sufficient sample of blood that one can get from pricking one's finger with a needle. In theory, you or I could use a lancet to gather a few drops of blood, drip them into a vial, and mail them off to a lab to be cultured for later use.

This dovetails with an article in the Smithsonian that came out last month that I've been sitting on while waiting for the right kind of information to pair it with. One Elizabeth Holmes has spent the past decade working on something she calls Theranos, a technology and set of techniques which make it possible to execute several dozen diagnostic tests simultaneously on a single drop of blood collected with a fingerstick instead of several vials of blood drawn by a trained phlebotomist. Her technology is proprietary so we don't have a whole lot of information on how it works, but I think we can make an inference or two. The extremely small quantity of blood required (one one-thousandth of the blood required for a full blood panel) suggests that they're using some sort of advanced lab-on-a-chip technology (which is pretty much what it says on the tin - full laboratory procedures built onto a single chip rather than a lab workbench loaded with equipment). The speed required to run the tests is also at least an order of magnatude faster - 30 tests can be executed in less than a day (including follow-up assessments and double checking) as opposed to a week or so in conventional labs. The results are sent back to the patient's physician or specialist for interpretation, but I see no reason why the patient can be CC'd on the e-mail as well. The list of tests is quite impressive: Everything from serum amphetamine levels to anti-thyroglobulin antibodies, a basic metabolic panel to blood typing, to DNA antibody detection and HIV screening. It is also very interesting to note that the costs of the tests are small fractions of what they would cost at a lab or in a hospital - quantitative HIV screening, for example, costs $59us, and a comprehensive metabolic panel costs about $6us. If I happen to be in the area of one of their offices I'll get some tests done and write an article about it.

More under the cut...

The Doctor | 19 April 2014, 14:00 hours | default | No comments

Someone in the community needs help.

I don't have a whole lot of time right now, but this came to me via several channels that I trust. Robert Mathis-Friedman suffered a massive stroke in December of 2013. Following major brain surgery and months of occupational and physical therapy, he's home from the hospital but his family are asking for donations to help modify his house so that he can lead a more active life.

If you can donate some money, please do so to help him.

The Doctor | 16 April 2014, 22:28 hours | default | No comments

A little forewarning is better than none at all.

Set a Google Alert on the phrase "we take security very seriously" and leaf through it every time you get hits. Often, if a popular website gets compromised, they'll post about it on their blog a couple of days before the e-mail announcement hits your inbox. It may not buy you a lot of time but two days is better than none at all.

The Doctor | 12 April 2014, 13:49 hours | randomknowledge | No comments

Heartbleed mitigation in place.

I've updated the SSL certificate on my website as a response to the Heartbleed vulnerability.

Relevant information on the new certificate is here, PGP signed with my usual key (0x807B17C1 / 7960 1CDC 85C9 0B63 8D9F DD89 3BD8 FF2B 807B 17C1).

The Doctor | 09 April 2014, 10:42 hours | default | No comments

Ubuntu Linux and the Heartbleed OpenSSL vulnerability.

If you're in the mad scramble to patch the Heartbleed vulnerability in OpenSSL on your Ubuntu servers but you need to see some documentation, look in your /usr/share/doc/openssl/changelog.Debian.gz file. If you see the following at the very top of the file, you're patched:

openssl (1.0.1-4ubuntu5.12) precise-security; urgency=medium

* SECURITY UPDATE: side-channel attack on Montgomery ladder implementation
- debian/patches/CVE-2014-0076.patch: add and use constant time swap in
crypto/bn/bn.h, crypto/bn/bn_lib.c, crypto/ec/ec2_mult.c,
- CVE-2014-0076
* SECURITY UPDATE: memory disclosure in TLS heartbeat extension
- debian/patches/CVE-2014-0160.patch: use correct lengths in
ssl/d1_both.c, ssl/t1_lib.c.
- CVE-2014-0160

-- Marc Deslauriers Mon, 07 Apr 2014 15:45:14 -0400

If you don't, run sudo apt-get update followed by sudo apt-get upgrade -y and then reboot the machine to make sure everything linked against OpenSSL gets restarted and uses the new code. Better safe than sorry.

The Doctor | 07 April 2014, 22:51 hours | default | One comment

There's wearable computing, and then there's wearable computing.

Just last year around this time the company MC10 figured out how to fabricate small networks of sensors built out of flexible circuitry that stick to the skin of the wearer and collect biotelemetry. By sticking a single square of wavy, flexible circuitry someplace on your person you could keep a medical team appraised of certain aspects of your health. The tech curve, as always, moves like a roller coaster gone out of control... in the journal Nature Nanotechnology a research team at the Swiss Federal Institute of Technology improved upon the design and created flexible circuitry tattoos that can store data on-board and dispense drugs in response. The 4cm by 2cm prototypes are a third of a millimeter thick and are externally powered (they don't yet have on board power supplies), and consist of circuitry fabricated out of new flexible nanomaterials. The current prototypes are unique in that they have non-volatile memory built in, implemented in a technology called resistive RAM, which has some remarkable functional properties in and of itself...

This latest generation of functional prototypes has much more processing power than those built just a year ago and use less energy. The tradeoff for that added functionality, however, is that power has to be supplied wirelessly from an external unit. The current prototypes are capable of recording and analyzing certain aspects of the wearer's metabolism and can react by delivering drugs under certain conditions. Projected use cases for more advanced versions of the wearable tattoo/computers (at the rate things are going, give it eight months or so) involve recognizing biosignals characteristic of certain conditions (such as seizures) or changes in hormone levels and treating them in near-realtime. It seems reasonable to hypothesize that one of the first improvements will be the addition of on-board power to make them more stand-alone, and I'd be surprised if somebody didn't try to give a model after that a Bluetooth-compatible transceiver chipset so that it could communicate with a hand-held computer or smartphone. This is already being done with insulin pumps so it's not much of a stretch to say that one could be added to a test type biomonitoring applique'. Fitbit users, time to keep a sensor net trained on Amazon's list of new products...

The Doctor | 03 April 2014, 10:15 hours | default | No comments

Prosthetic synaesthesia and cortical implants.

The human brain is a remarkably complex and flexible organ, with as many possible failure modes and glitches as there are emergent and surprising properties. Take something away, and sometimes you can coax another part of the brain to take up the slack in some other way. Case in point, artist Neil Harbisson. Harbisson was born with a condition called achromatopsia, which is the name for a group of disorders which collectively result in the same phenomenon - he cannot see colors, only shades of greyscale. Sometimes it's a neurological dysfunction, sometimes it's a defect in the retina, and sometimes it's due to some other combination of factors. In a decade-long experiment, Harbisson developed a prosthesis which incorporates a high resolution camera, a small radio scanner, and a microprocessor which converts patterns of color and RF emissions into patterns of sound. Over time, he's trained his brain to interpret those patterns of sound into a form that he can use to create his art. Some might say that he's trained himself to have a form of synaesthesia, or a state in which sensory modes are combined in unusual ways (such as seeing geometric or colored patterns when hearing certain sounds, or tasting phantom flavors when touching things with different textures). Recently, to increase the resolution of the new sensory input he had a new version implanted into his skull. The implant is much more sensitive, and its placement in his skull will give him much depth of sensation.

Of what use might this be to someone who isn't an artist? Ask someone who has a magnet implanted in their finger how useful it is when debugging power supplies.

More under the cut...

The Doctor | 01 April 2014, 09:00 hours | default | No comments

Turtles All the Way Down: So, does anyone actually operate this way?

So, after all everything's said and done, you're probably asking yourself "Why would somebody go through all this trouble to build a computer from the ground up? It's never going to be as fast as one that you can buy, so what's the point?"

Ultimately, it comes down to what you're trying to accomplish. If you want the fastest possible CPU, tens of gigabytes of RAM, and four monitors so you can go raiding more efficiently chances are you have a threat model that doesn't approach the level of concern, paranoia, or security requirements that we assumed through the other articles in this series. If you're hoping to precisely replicate a customized laptop to run half a dozen virtual machines, an office suite, and a visual IDE you will probably be disappointed. I have no idea if it will be possible to run a virtualization stack like QEMU or even DOSbox on our free and open laptop. If you're looking to learn how computers operate from the ground up this is a good project; it might even make a good class project that covers a semester or two. If you're willing to trade off raw processor speed for visibility into the CPU's inner workings, a gig or two of RAM to be able to modify and upgrade every last aspect of the motherboard and interfaces, and no (or little) 3D acceleration for a platform that you're much more certain hasn't been compromised in subtle ways, this might be a project of interest (especially if your threat model fits the last 'if'...)

Let's face facts. When working with computers we are forced to make many trade-offs. Code in a language which incorporates many features that let you precisely specify certain functionality and you might be trading off readability. Program in a language which is relatively simple and orthogonal and you'll be trading off by having to write more code later to carry out certain tasks. Ease of use and increased security measures are a trade off that we all make, one which frustrates many end users and causes people to pick legendarily bad passwords. Use a graphical user interface and you often trade off for visibility of inner workings and configurability (though good arguments have been made for the former, even I have to admit). Unfortunately we can't have everything both ways, as much as we might tell ourselves that we can. So, let's consider a couple of real-life case studies of some platforms and use cases that seem inconveniently limited or inordinately difficult to use.

More under the cut...

The Doctor | 28 March 2014, 09:30 hours | content | One comment

Turtles All the Way Down: Applications

Now our hypothetical trusted and open computing platform needs applications so you can get real work done. Text editors, scripting languages, officeware, and probably a desktop of some kind. To stick with our security practice of keeping systems as spare as possible, I recommend only installing applications and their dependencies as you need them. In the last post I suggested picking a package management system of some kind if one isn't already a core component of the OS that we recompiled and installed. If you get in the habit of building and using packages now you'll save yourself a lot of heartache later. Trust me on this.

More under the cut...

The Doctor | 24 March 2014, 09:00 hours | content | One comment

Enhanced prosthetics, cryptographic music collectives, and custom-built cardiac assist devices.

When many people consider prosthetic limbs, they often seem to think of mechanisms that replace some of the functions of the original but don't seem to add anything new. Prosthetics limbs are not very common and they're almost always very expensive. To the best of my knowledge I don't know of anybody modifying a prosthetic in any substantial way (or any way, for that matter). That's what made this news article jump out at me: A student at the Atlanta Institute of Music and Media named Jason Barnes lost his right arm in an accident in the workplace. He wears a prosthetic hand which seems to serve him well, but it doesn't have all of the flexibility of the original which makes playing the drums difficult. Gil Weinberg of the Georgia Center for Music Technology wrote a proposal for and recieved a grant from the National Science Foundation to fund the development of the Robotic Drum Prosthesis, which is a custom-designed replacement hand that not only grips a pair of complimentary positioned drumsticks but also has enough processing power on board to make the playing of second drumstuck autonomous. The microprocessor on board analyzes Jason's percussion routines and improvises a third percussion line automatically played by the other drumstick controlled by the prosthesis. Not only is Jason able to play the drums and marimba more effectively but he's never quite sure what he's going to get...

Wanting to play in a band isn't an easy thing. First, you have to figure out where your musical talents lie; not everybody's are conducive to playing live, or playing pre-recorded, or even playing alongside others. Some people's gifts lie in fields other than music which are no less important, I hasten to add. So, you have to figure out not only where you fit but you have to find (or avoid) collaborators. Then you have to figure out how to market yourself so you get people listening to your work, and distribute your work, and and and... It's hard. I was never able to pull it off, which is probably why I'm sitting on my couch writing blog posts and not on the road touring. I realize that I'm making this about me, which is something I don't ordinarily do but I've got good reason to this time. What if it was possible to find some combination of musical and sapient factors to make it more feasible to play as a musician?

Enter the Cypherfunks.

More under the cut...

The Doctor | 17 March 2014, 10:00 hours | default | Two comments

Electrical relief of migraines, advances in bioprinting, and prosthetic exoskeletons.

If you've never had one before migraine headaches are no picnic. Between the feeling like somebody's testing a sawmill with part of your skull, profound nausea brought about by something as innocuous as sunlight or the sound of a diesel engine, and vertigo that makes walking to the bathroom to retch a challenge, they're something that many of us would probably not wish on our worst enemies (I know I don't). There are few things that can arrest or lessen the severity of migraines once they start. Mostly, all you can do is get someplace dark and quiet and ride it out, maybe with a handful of analgesics that never seem to do anything other than upset one's stomach. Last week, however, the US Food and Drug Administation OK'd an electrostimulation device that has been shown to prevent migraines. Called the Cefaly, it's a tiara containing a TENS-lie electrostimulation device that acts upon the trigeminal nerve and a microprocessor that seems to modulate the electrostim signals based upon feedback from the trigeminal nerve itself. It's available for sale at this time; believe you me, I thought long and hard about ordering one. On the other hand, I don't get migraines often enough to justify the purchase, and I'd much rather that somebody with chronic migraines had access to it. So, to everyone out there who suffers from chronic migraines, you may wish to pay your physician a visit and make some inquiries.

If you've been following the field of 3D printing for a while you've probably come across articles about bioprinting: Fabbers which build living tissue layer by layer by depositing living cells in the appropriate order. At the Wyss Institute for Biologically Inspired Engineering at Harvard University a bioprinting research project has figured out how to fab more elaborate biological constructions. In the lab they've been able to fabricate layers of tissue thicker than an American dime by using three bio-inks, two of which contain living cells and a third which liquifies and drains away as it cools, leaving channels running through the fabbed tissue which are perfect for blood vessels to be grown. This fixes the problems of not getting oxygen and nutrients into the deeper layers of the tissue because they're not exposed, and evacuating wastes and carbon dioxide from the tissue as the cells metabolize. The research team's prototypes have gotten progressively complex, and the paper they've published in the journal Advanced Materials states that this is the closest they've come to naturally grown tissue yet.

In yet other 3D printing news, Amanda Boxel was rendered paraplegic after a skiing accident in 1992.ev. A couple of weeks back she was able to leave her wheelchair and walk again with the mechanical assistance of the Ekso-Suit, a powered exoskeleton fabricated on a 3D printer. The device was custom fit for her body with data from a full-body 3D contour scan. Amanda requires the use of forearm crutches to balance herself, I would hypothesize after watching the demonstration video because the Ekso-Suit doesn't seem to have any visible mechanisms for balancing though the legs appear strong enough to support her weight. It's certainly worth watching the video to see her stand up and walk across the stage. Construction of the Ekso-Suit requires approximately three months, which includes running the individual components off, assembling them, and build the wiring harnesses for the control mechanism and the servomotors. The computer and power cells for the unit appear to be mounted on the wearer's back (reasonable when you take into account distribution of weight and counterbalance and ergonomic concerns).

The Doctor | 16 March 2014, 22:17 hours | default | No comments

Self censorship.

How many things have you started to write and stopped because you were afraid of who or what might read them? How many blog posts have you shelved, how many files have you deleted, how many pages have you burned because you feared what might happen if the wrong person or wrong thing spotted them and decided to make an example of you?

Have you ever wondered what the criteria might be under which a message in a chat room might trigger increased scrutiny, like mysterious malfunctions of your computer?

How many fears have you not expressed or opinions have you kept to yourself because you feared what might happen the next time you tried to board a plane?

We now live in a time in which the most paranoid rantings pale in comparison to the reality.

We're back to the days of "Don't do that, you'll wind up on a list, and you'll be in trouble when They need to clean it." We're back to the days of remaining silent because we fear what may happen one night.

The Doctor | 16 March 2014, 21:07 hours | default | Two comments

I'll be presenting at the Global Existential Risks and Radical Futures Conference

I have other stuff to write about that will come in time.

I'll be presenting at the Global Existential Risks and Radical Futures Conference in San Francisco, CA on 14 June 2014. I'll be giving a talk entitled Echos Into the Past: Outbreaks of Future Technologies in the Present, about technologies that exist right now which the transhumanist community may wish to consider as first steps toward long-term goals.

The Doctor | 13 March 2014, 11:23 hours | default | No comments

Turtles All the Way Down: Bootstrapping an operating system.

Now we need an operating system for the trusted, open source computer. As previously mentioned, Windows and MacOSX are out because we can't audit the code, and it is known that weaponized 0-days are stockpiled by some agencies for the purpose of exploitation and remote manipulation of systems, and are also sold on the black and grey markets for varying amounts of money (hundreds to multiple thousands of dollars). It has been observed by experts many a time that software being open source is not a panacea for security. It does, however, mean that the code can be audited for bugs (vulnerabilities and otherwise) via any number of methods, from manual inspection to dynamic analysis. It also means that the OS and its associated applications can be ported to platforms it's not already available on. And, let's face it, the chances that Microsoft will port Windows to our trusted open source platform are Slim and None, and Slim's in his hotel room in Berlin recovering from CCC.

So, what are our options?

More under the cut...

The Doctor | 10 March 2014, 09:00 hours | content | No comments

Taking a brief break.

Wrists bothering me again. Leaving blog posts to a net.spider so the RST will ease up a little. Writing the new generation of them is taking a toll.

The Doctor | 03 March 2014, 23:10 hours | default | No comments

Turtles All the Way Down: Firmware and bootloaders.

After rethinking this post a little, I feel a need to caveat things: In a previous post in this series I mentioned the possibility of using an open source System On A Chip because it would simplify the construction process somewhat. I've been doing some more research and I'm not certain that all SoC's (if that is the direction a project like this would go in) require system firmware of the sort we're about to discuss. The Broadcom BCM2835 mentioned earlier, for example, has firmware on board that is sufficient to initialize the hardware and then try to load the OS from an SD card, and that's about it. It doesn't seem to use anything even vaguely PC-like insofar as the early stages of the boot process are concerned. So, let's cover this ground because it may be necessary, and if it isn't it would be handy to have some knowledge of a few open source projects that don't get enough attention. If it's not necessary, then we'll figure out what is when the time comes.

Moving up the stack, now we need core code - a set of instructions that the computer loads into memory and executes to bootstrap the rest of the system, starting with initializing a basic set of peripherals and activating the boot loader. PCs have a BIOS, which you've probably encountered when playing around with your machine's configuration. Apple computers use something different that does much the same thing called UEFI (Unified Extensible Firmware Interface). Sun servers used OpenFirmware for this purpose, which is incidentally open source and bears a BSD license. Examples given, we need something that does the same job that we have transparency into the inner workings of.

More under the cut...

The Doctor | 26 February 2014, 09:00 hours | content | Six comments

Senator Wyrmser explores the American Southwest.

When Jason and I set out for the west coast in October of 2013, we drove cross-country with a Scalemate plushie named Senator Wyrmser riding shotgun for us. He quickly became something of a mascot for the trip, and every morning we'd set out with a cheerful "Squeaka!" from our traveling companion. The last thing I expected was the little guy setting out on his own while Jason and I were visiting the gift shop at the Petrified Forest. I found some of his vacation selfies on my camera last night, and it seems that he did a good job making friends while we weren't looking.

The Doctor | 24 February 2014, 13:36 hours | images | No comments
"We, the extraordinary, were conspiring to make the world better."