Computer viruses, spam, and computer hacking are so common that keeping computers and networks safe from attack is a billion-dollar industry.
But if some Sandia researchers successfully change the way software is written, the antivirus industry will become obsolete. By “embracing” the complexity that characterizes computer systems, the new software will render computers much safer from cyber attacks.
A Laboratory Directed Research and Development (LDRD) study guided by Jackson Mayo (8963) and Rob Armstrong (8961) is applying complex-system theory to cyber security. The mathematical properties of complex systems, Jackson says, are vexing for programmers since writing perfect, bug-free software is generally futile.
But Jackson and his colleagues have a novel approach to cyber security. Instead of fighting computer complexity, they advocate embracing and structuring a computer’s complex features to create an excruciatingly thorny problem that is virtually impossible for cyber attackers to solve.
“One way to describe a complex system is something, such as a computer, that can perform arbitrarily complicated calculations,” Jackson explains. “The behavior of a single transistor out of millions can change a calculation’s results.”
Rob likens complex systems to biological organisms.
“Complex systems, whether cyber or biological, are constructed or evolve to solve problems,” he says. Networked computers have been engineered to best participate in the information economy, he says, and living organisms have evolved to solve the problem of survival.
The same complexity required for problem-solving leaves complex systems susceptible to attack. There is no methodology, Rob notes, that can guarantee the absence of vulnerabilities in complex hardware or software; this is an implication of a mathematical theorem known as Turing undecidability. However, an attacker needs to find only one vulnerability to compromise a system. This “asymmetry” of cyber warfare is compounded because identical copies of hardware and software are used across the Internet. Thus, a single vulnerability can lead to a massive shutdown since all copies can be attacked in the same way.
According to Jackson, software developers can exploit complexity to confuse and deter potential attackers. “What we advocate is developing software and systems that are extremely complex but more difficult to attack than simple systems.”
Complex systems, Jackson explains, contain many elements with seemingly chaotic interactions. These interactions produce “emergent behaviors” that impact the whole system. So one key to preventing virus and spam replication is understanding and modeling these emergent behaviors.
Jackson and Rob have many concepts for relating software to the broader complexity field, including analogies to phase transitions and biochemical networks. But one approach they consider promising performs an “end run” around the overwhelming complexity of software, by exploiting an ensemble of many similar systems to make stronger statements than they could about any one member.
A key tenet in Jackson and Rob’s work is “robustness,” the concept that compromise of a single component should not trigger complete system failure. An ensemble of replicas doing the same job in tandem is one generic way to achieve robustness. But multiple computers running identical software will encounter the same bugs and produce the same faulty or even dangerous output.
A possible solution, Jackson says, is to achieve “robustness through diversity in software” by writing different software versions so that there are few or no bugs in common. In operation, the same input is fed to each of them and the outputs are compared to identify and eliminate compromised versions. “This is the leading approach we have in mind for achieving robustness in software systems,” he says.
Exponential increases in effort required
The potential benefits are great, Jackson and Rob say, because the effort required for a hacker to infiltrate such an ensemble grows exponentially with the number of software versions. “The hacker essentially has to look for a very tiny point in space where everything magically fails at once, and that’s very hard to do,” says Jackson. A key advantage of diversity, he notes, is that it offers protection even if the attacker knows exactly how the system is constructed.
The approach has challenges, Jackson acknowledges, since replicating software programs requires extra time and resources, and it’s difficult to know how many versions are needed. But he says replication can be achieved through automatically generated software versions, which are already available in some computer languages or even genetic-programming techniques that work like biological mutations, making multiple but very slight modifications to create new, random software variants.
An extended form of the concept, “in-depth robustness,” is derived from redundant array of independent disk (RAID) theory — using distributed redundancy to achieve computing efficiency. In-depth robustness can be created in software by partially overlapping calculations and distributing multiple cross-checks within a program.
Jackson and Rob say that current virus- and spam-fighting efforts have failed to confront the essential complexity of computer systems — specifically, the reality that complex systems cannot be “reductively” analyzed. In other words, simply averaging individual behaviors will not accurately describe the overall behavior. But by using what they call a “renormalization” technique, the team can identify natural units that interact within the system; this is one way to achieve a realistic picture of emergent behaviors.
For example, says Jackson, a computer with many transistors on a chip may show natural divisions. “So there’s one little cluster here that acts as a unit and does a lot of things inside itself but only occasionally interacts with others, and then you have another cluster and another.” Those clusters, he says, can each be modeled at a higher level. As long as the model retains enough complexity, it will eventually reproduce the behaviors of interest.
In the simplest terms, Jackson and Rob’s work uses complexity and emergent-behavior theory to make computer systems exceptionally difficult to attack successfully.
“We’re taking a very high-risk — but potentially very high-payoff — approach,” says Jackson. “While the work might not be something we can translate into a practical application and sell to Microsoft right now, we know there’s a problem in computing that isn’t being addressed. Complexity is the problem, but it’s also the solution. By studying complexity, we will be ahead of the curve.”