אליהו א. סולטניק, Ph.D.

Evan's First Name @ Sultanik .com

מדען ראשי
Digital Operatives, LLC

מרצה מן החוץ
אוניברסיטת דרכסל
החוג למדעי המחשב

Recent Content:

PoC‖GTFO Issue 0x14

PASTOR LAPHROAIG SCREAMS HIGH FIVE TO THE HEAVENS AS THE WHOLE WORLD GOES UNDER

Is Automation of Automation Going to Kill Off Computer Science Jobs?

An Essay in Polite Dissent to Mark Cuban

My friend, colleague, and homonymous intellectual doppelgänger Evan Teran always likes to remind me of Betteridge’s law of headlines:

The answer to virtually every clickbait title that asks a yes/no question is: “No.”

Mark Cuban, in an interview on Bloomberg TV, claimed that the next wave of automation will be “the automation of automation.”

By that, Cuban means software will soon begin writing itself, which will ultimately eliminate those lucrative software development jobs. About writing software, Cuban said: “It’s just math, right?” Humans will no longer be needed.

Hold my beer, I’ma explain some math.

Remember The Imitation Game? The Academy Award winning movie from a few years back, starring Buttercup Cummerbund and British Natalie Portman? It was loosely based on Alan Turing’s groundbreaking work cracking the Nazis’ cryptographic codes, helping the Allies win the war. That very same dude is much more famous among mathematicians and computer scientists for his work on the Halting Problem.

The Halting Problem dates back to the seventeenth century, from none other than Gottfried Leibniz—the same dude who independently discovered Calculus, even though Isaac Newton usually gets all the credit. Leibniz dreamt of building a machine that could automatically check whether mathematical formulas were correct or not. If you’ve gathered by this point that mathematical formulas are effectively the same as computer programs, then congratulations! Take a sip of my beer as a reward.

If you’re familiar with the Halting Problem, you can probably already see where I’m going with this argument. I’ve been asked why I chose to use the Halting Problem as a basis, as opposed to going the route of simply—and correctly—arguing that creating software is an immensely complex engineering problem whose configuration space is exponential. If the reader is technical like you, then they undoubtedly already know this. If, however, the reader is not familiar with any of these concepts, then I have found that it is very difficult to overcome the public’s incorrect perception that computers will continue getting faster and faster and, therefore, will eventually be able to do anything. As if hardware speed alone is what provides “intelligence.” It’s very difficult to convince people otherwise, since it basically requires teaching P vs. NP. Therefore, it is a much simpler rhetorical task to demonstrate that there are clear, fundamental limits to what computers can even compute, meaning that computers provably can’t make a perfect mapping from imprecise specifications into a sufficiently correctly functioning program. There needs to be some “intelligence” in the equation: either a programmer or strong AI.

Fast forward to the early 20th century, and a sort of revolution was going on in the world of mathematics: New systems were being developed to formally encode logic. Think of it like the system of algebra you learned in grade school, except that instead of numbers you’re working with logical statements. David Hilbert was at the forefront of this research, and in 1928 posed the question: Is it possible to devise an algorithm (vi&, a computer program) that can automatically determine whether a given logical statement is universally valid? This became known with the extraordinarily Deutschtastic name „Entscheidungsproblem“. A few years later, Austrian expat Kurt Gödel—who is also famous for discovering a “bug” in the US constitution at an immigration court appearance with Albert Einstein—proved that the answer to the entscheidungsproblem is: No, it is provably impossible. In his seminal paper titled „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“, he shattered the entscheidungsproblem both in theory and in Deutschtasticness.

So, back to Turing. A few years later, but before the events that inspired The Imitation Game, Turing created a mathematical definition of a computer which we now call a Turing Machine, and on which practically all modern computers and computer science is based. Turing realized that the logical statements and algorithms Hilbert and Gödel were working with were in fact no different than the programs that could be computed by his Turing Machine. He then restated the entscheidungsproblem in this context: Is it possible to write a program for a Turing Machine that can take another program and that other program’s input and automatically determine whether that other program will terminate? This became known as the Halting Problem and, just like the entscheidungsproblem, Turing was able to prove that the answer is “No”: It is impossible to create a program that can automatically determine whether another program will terminate.

Please indulge me as I briefly delve into metaphysics and, dare I say, even digital physics. Can our universe be described using logic and/or computation? In other words, if there were some infinitely powerful Turing machine, could one write a program to run on it such that it could accurately simulate the entire universe? If so, then we humans are bound by the same theorems that prove mathematical logic is incomplete and that the Halting Problem is undecidable. In other words, it’d be impossible for even humans to prove that a given program is correct.

The Halting Problem is part of what makes programming computers hard: Any program with even a modicum of real-world complexity cannot have provably correct behavior. Those logical flaws and unintended behaviors are precisely what hackers exploit to make programs do things that the programmer never intended. Human programmers are only able to do a passable job of quality control because we have the benefit of heuristics and instincts that are guided by our general intelligence.

Let’s say we develop a computer program that can take a human’s high-level description of a task and automatically generate a computer program that can complete that task. There are two possibilities:

  1. the human is specifying all of the complex logic, and the computer is simply translating that specification into a program by rote; or
  2. the human is not specifying any complex logic, and the computer needs to determine the logic that needs to be in the program to accomplish the task.
The first possibility is effectively describing a human computer programmer and compiler. The second possibility is what Cuban seems to be describing. The trouble is that, by virtue of the Halting problem, no such program could ever determine whether its output is correct! Furthermore, automatically determining the logic that needs to be in a program to accomplish a given task is provably computationally hard, and cannot be solved in general in a reasonable amount of time, regardless of how fast computers get.

Could I write a program that accepts inputs like, “Create a program that displays pictures of cats,” and then automatically generates a program to do so? Sure. Could I create a program that automatically creates a program that is able to interface with the highly formally specified interface of another automatically generated program? Probably. But the vast majority of software projects are for solving complex human problems, and typically involve integration with numerous legacy programs and software that were written by crazies, idiots, and crazy idiots. Professional programming sucks. Don’t believe me? If you take away nothing else from this essay, please read this article. I’m serious, read it. Any professional-grade program that can automatically generate other programs will have to grok how to interface with the undocumented source code of other humans. That’s impossible unless the computer is intellectually indistinguishable from a human.

In order for a computer to automatically generate a program that solves a human’s problem, there either needs to be a human deciding the logic (i.e., a programmer), or the computer’s intelligence needs to be indistinguishable from that of a human. And if we have computers that are intellectually indistinguishable from humans, we’ll have more issues to deal with than simply losing software jobs.

PoC‖GTFO Issue 0x13

PASTOR LAPHROAIG'S MERCY SHIP HOLDS STONES FROM THE IVORY TOWER, BUT ONLY AS BALLAST!

PoC‖GTFO Issue 0x12

COLLECTING BOTTLES OF BROKEN THINGS, PASTOR MANUL LAPHROAIG WITH THEORY AND PRAXIS COULD BE THE MAN WHO SNEAKS A LOOK BEHIND THE CURTAIN!

PoC‖GTFO Issue 0x11

IN A FIT OF STUBBORN OPTIMISM, PASTOR MANUL LAPHROAIG AND HIS CLEVER CREW SET SAIL TOWARD WELCOMING SHORES OF THE GREAT UNKNOWN!

PoC‖GTFO Issue 0x10

IN THE THEATER OF LITERATE DISASSEMBLY, PASTOR MANUL LAPHROAIG AND HIS MERRY BAND OF REVERSE ENGINEERS LIFT THE WELDED HOOD FROM THE ENGINE THAT RUNS THE WORLD!

PoC‖GTFO Issue 0x09

PoC ‖ GTFO PASTOR MANUL LAPHROAIG'S TABERNACLE CHOIR SINGS REVERENT ELEGIES OF THE SECOND CRYPTO WAR

PoC‖GTFO Issue 0x08

AS EXPLOITS SIT LONELY, FORGOTTEN ON THE SHELF YOUR FRIENDLY NEIGHBORS AT PoC ‖ GTFO PROUDLY PRESENT PASTOR MANUL LAPHROAIG'S EXPORT--CONTROLLED CHURCH NEWSLETTER

Service Discovery on Dynamic Peer-to-Peer Networks Using Mobile Agents

or, How Bumper Cars Relate to Computer Science

The absurd realization that it has almost exactly been a decade since I defended my master’s thesis took me by surprise. It seems like yesterday. That work has had some decent exposure over the years, but, like most creative works produced toward the beginning of one’s career, I do not look back on it as a paragon.

Moshe Kam, upon reading a preliminary draft, summarized it very well:

[It] reads like Tristram Shandy, but devoid of humor.
He was referring to my organization of one particular chapter: First I described the overall technique, then I proceeded to iteratively break the problem into successively smaller chunks. A bit like taking apart a matryoshka doll. Or maybe a more apt analogy would be: peeling away the layers of a rotten onion only to find a miniscule, barely salvageable core, calling into question the cost/benefit of the whole excavation. Moshe was right. With that said—and unlike the eponymous biographee of the aforementioned book—I think I can at least claim that my ideas are fully “born” in the first volume.

Despite somehow managing to get that chapter of my thesis published in a book, I feel like it always suffered from my cumbersome presentation. Therefore, perhaps inspired by Stetson hats and hip flasks, I have since devised an analogy that I hope at least makes the problem (if not my solution) more accessible. That’s what I am going to describe in the remainder of this post.

Consider, for a moment, that you are piloting a car in a huge bumper car arena.


CC BY 2.0, adapted from here

You have some control over your own movement, but there are so many others driving around in the arena that there are constant, unavoidable collisions that throw you off course. From afar, everyone’s movement seems random.

The challenge is that you need to know the time, but you do not have a watch. In fact, there are very few others that have a watch. How do you find the time?

The naïve solution is to simply yell out, “Who has the time‽” The problems with this solution are:

  1. If everyone needs to know the time at once, there will be very many yelling people.
  2. What if no one with a watch can hear you? Bumper car arenas tend to be loud.

A slightly more intelligent approach might be to:

  1. Take a piece of paper and write a request on it for the current time.
  2. Pass the piece of paper to the next person who bumps into you.
  3. If one who is watch-less receives such a piece of paper, he or she passes it on to the next person that bumps into him or her.
  4. When the note eventually reaches someone with a watch, he or she will write the current time on the piece of paper and send it back to you.

The obvious shortcomings to this approach, however, are that:

  1. When the note eventually gets back to you, the time will be incorrect!
  2. What if, in fact, no one has a watch? How long do you have to wait without receiving a response before you can be sure that no one has a watch?
  3. What if not everyone speaks and/or reads English?

My realization is that: If one roughly knows the topology of the network (i.e., the locations of all of the cars), and if the messages are truly passed randomly through the network, one can use ergodic theory and random graph theory to accurately predict the frequency of message arrivals. Assuming knowledge of the network topology is reasonable, since many ad hoc networking algorithms already provide it. Even if it is not available, an approximation of the topological properties is often sufficient. So, what this provides is a model for predicting how long it will take for one’s message to eventually reach someone with a watch and, subsequently, how long it will take for the response to be returned. What I discovered was that the variance is often small enough such that this estimate can be used to correctly adjust for the delay in returning the time. Furthermore, this model provides a probability distribution for how likely it is that one would have received at least one response as a function of waiting time. Therefore, if n seconds have passed and the model says that with probability 0.99 one should have received a response to the time query, yet no response has been received, one can conclude with 99% certainty that there is no one in the network with a watch!

The last challenge question, “What if not everyone speaks and/or reads English?” will have to wait for another post…

Positive Train Control

or, Jet Fuel Can’t Melt Train Tracks

It’s been a week since the tragic Amtrak derailment in my home town of Philadelphia. Being an avid train passenger—commuting to and from DC several times per week—and having taken the ill fated Northeast Regional Train No. 188 on multiple occasions, this has struck close to home. I am posting this blog entry from the café car of Train No. 111, the first Southbound train to commence full Amtrak service since the disaster.

I realize that it is very early, and the National Transportation Safety Board investigation is still ongoing. Speculation—especially by someone like me who is not a transportation expert—would be unproductive at best, and offensive to the victims at worst. Perhaps it’s my job as a security professional—in which I am paid to find vulnerabilities in systems … or perhaps it’s the recent spate of news that both cars’ and even commercial airplanes’ heavily computerized control systems can be commandeered, wirelessly, by a remote attacker … or perhaps it is the fact that the crash occurred immediately after national rail safety week and on the eve of a legislative debate on cutting Amtrak funding … or perhaps I’ve just been reading too much Pynchon… but ever since I heard that the train was speeding and that there is no direct evidence incriminating the train operators of negligence (other than the speed), the first thing that popped into my mind was: Software. I haven’t heard anyone (other than well-known security expert Simson Garfinkel) discuss it, so that’s what I’m going to do in the remainder of this post.

One topic that the media has latched onto is Positive Train Control (PTC): a technology that, if only it had been implemented, is purported to have been able to avert the crash. What the media doesn’t say is that the ACS-64 locomotive that was pulling the fateful train was already equipped with PTC. You see, the Advanced Civil Speed Enforcement System (ACSES)—Amtrak’s version of PTC for the Northeast Corridor—requires components both on-board the locomotive and wayside (on the tracks). In other words, PTC will only be fully functional if both the locomotive and tracks are upgraded. Portions of track South of Philadelphia and North of New York already have support. In the case of the Philadelphia crash, the locomotive was a new model that had support, but the tracks on which it derailed did not.

I contend that a software bug in the ACSES system should not be ruled out as a potential cause of or contributing factor to the derailment. Let me be clear: I am not claiming that software was a likely cause of the crash. I am neither a transportation expert nor do I have any detailed knowledge of the ACSES implementation. The purpose of this article is to provide enough evidence that software errors are a plausible enough explanation that the possibility should at least become a part of the public discussion.

There is a reasonable precedent of software bugs causing physical catastrophes. For example, a software bug in Toyota’s electronic throttle control system recently caused the massively publicized “unintended acceleration” problem in many of their vehicles, killing at least 89 people as a result. In 2007, a group of six F-22 Raptor fighter jets experienced multiple computer crashes coincident with crossing the international dateline caused by a software bug that did not anticipate that corner case. The planes lost all navigation and communication, and were only able to make it back to land by following their tankers. Vehicles and transportation systems in general are so complex, automated, and computerized these days that a single software bug can wreak havoc.

But how could a system that is intended to provide a safeguard against crashing actually cause a crash?

A relatively recent report to congress by the Federal Railroad Commission on the implementation of PTC states that ACSES has control over the

…event recorder, train line data sensors, horn circuit, brake systems, cab signal system (if equipped), and the Communication Segment.
So, presumably, the system has no control over acceleration, just deceleration.

I am perhaps about to delve too far into the sea of speculation, but as James Burke so eloquently demonstrated, a failure in one system can cascade to cause failures in seemingly independent and unconnected others.

A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.
There is a display in the cab of the locomotive with a speedometer, looking something like this:


CC BY-SA 3.0, from here

When the track is PTC-enabled, there is a second speed readout on the bottom, showing the maximum speed allowed on the track. When the track is not PTC-enabled, the readout looks as pictured here. If the conductor or engineer is relying on that display to gauge the train’s current speed, he or she is thereby relying on the output of ACSES’s algorithms, programming, hardware, and sensors. A failure in any of those pieces could result in an incorrect speed readout, e.g., causing one to believe that the speed of the train were actually slower than in reality. This is similar to how Air France Flight 447 was doomed by an engineering design flaw in its airspeed sensors, which caused a failure in the autopilot software, which reported inaccurate instrumentation to the pilots, who relied upon the incorrect information, making manual piloting errors that caused the plane to crash.

I do not wish the tragedy of Amtrak Train No. 188 on anyone; it could have very easily been me sitting in that café car a week ago. While history has proven that human error is the most frequent cause of these types of accidents, we increasingly need to also look at the software for possible fault.