A catalog of software constructs, languages, and APIs that are unexpectedly Turing complete; the implications of this for safety and reliability. Application: how many computers in your computer?

Any fairly complex C or Fortran program contains a newly written, unspecified, buggy, and slow implementation of half of the Common Lisp language . - Tenth Greenspan Rule

Turing completeness (TC) is a property of the system to implement any computable function with some simple representation of input and output.

Turing completeness is a fundamental concept in computer science. It helps to answer many key questions, for example, why it is impossible to create the perfect antivirus program. But at the same time, it is amazingly commonphenomenon. It would seem that it is difficult for a computer system to achieve such universality that it can execute any program, but the opposite is true: it is difficult to write a useful system that does not immediately turn into a complete Turing. It turns out that even a little control over the input data and converting them into a result, as a rule, allows you to create a turing-complete system. It can be funny, useful (although usually not ), harmful or extremely unsafe and a real present for a hacker (see “language-theoretical security” , which studies hacking methods of “strange machines” ¹) Amazing examples of this behavior remind us that Turing completeness lurks everywhere, and it is extremely difficult to protect the system.

Too powerful programming languages ​​can also trigger unpleasant DoS attacks. Fazzer afl found such roff in OpenBSD that it is capable of generating an infinite loop , abusing some string substitution rules. Probably, these unexpected examples of Turing-complete systems are better considered as a subset of the “discovered” or “found” esoteric programming languages . So the extraordinarily minimalistic FRACTRAN is not considered ²

, as well as the specially obfuscated language Malbolge (where writing a trivial program will take years), because these are specially designed esoteric YaP. Also, the Life game is not included in our subset , because questions about Turing completeness appeared immediately after its release, and recognition of its complete Turing did not come as a surprise. And given the complexity of routing and packet switching networks, it is not surprising that a cellular automaton can be built on these networks or logic schemes can be programmed , and ticket planning / validation is not only an NP-difficult or even EXPSPACE-difficult task, but also completely unsolvable (due to complex airline rules).

Many configurations, special languages, tools, or complex games, as it turns out, violate the rule of least power and “accidentally become Turing complete” , like MediaWiki templates , sedor repeated regexp / find-replace commands in the editor. In general, any form of line replacement or templating, or compilation on the fly with a high probability is a Turing-complete system itself or when repeated, as they often support lambda calculus or rewriting of terms of a language or label, for example, esoteric languages ​​" /// " or thue .

XSLT ,Infinite Minesweeper , Dwarf Fortress ³, Starcraft, Minecraft , Ant , Transport Tycoon , C ++ templates and Java generalizations , DNA calculations and so on - all these are Turing-complete systems, and this is not surprising either. Many games support scripts to simplify development and custom mods. Therefore, to make the Turing-complete game elementary: just turn on the syntax to call more well-known languages ​​such as Perl.

Turing completeness may simply be a little-known part of the standard format. Probably, in our time, many do not know that TrueType and many fonts are PostScript programs on stacked machines, similar to ELF metadata and DWARF debugging information . Or whatsome music formats go beyond MIDI , support scripts, and need interpretation. If you know about the Turing completeness of fonts, then the completeness of Turing of TeX documents is not surprising, which naturally causes many serious and interesting security vulnerabilities in fonts and media, such as BLEND or Linux SNES and NES exploits . In other formats like PDF, there are just a terrible amount of vulnerabilities ⁴. Again, outstanding achievements like creating a small Turing machine from Lego blocks or dominoes ⁵are not considered, since we have long known how mechanical computers work.

On the other hand, a line of computer security research called weird machines often reveals truly amazing turing-complete systems. Moreover, they cause surprise to different degrees in different people: one seems unusual that does not surprise others.

• Peano arithmetic : addition and multiplication of natural numbers is enough for Turing completeness. On the contrary, Presburger arithmetic is devoid of multiplication and, therefore, is not Turing complete.
• Van tiles : multi-colored squares, the placement of which is determined by the rule that the adjacent sides of two tiles should be the same color (historically clear to Van, but the system surprised me, and probably many other people).
• x86 fraud:
  
  • MMU shuffles RAM to simplify programming. If the program correctly assigns addresses in memory in a special way, it will be able to perform arbitrary calculations on the MMU using page-faults exceptions ( comments ; scientific work ) without running the code itself. The MMU exception mechanism turns into a computer with one instruction .
  • movis a Turing-complete system : a seemingly innocuous assembler instruction movthat transfers data between the CPU and RAM, allows you to implement a computer with one instruction on the TTA trigger transport architecture . On such a computer, you can play Doom (as a bonus: on instructions xortoo).
  • "X86 is a turing complete set without registers."
• Return-into- libc attacks : software libraries provide pre-packaged functions, each of which is designed to do one useful thing. From calls to these functions, you can make a turing-complete “language” that can bypass security mechanisms, because an attacker does not run his own recognizable code. Among many other examples, see “The geometry of innocent flesh on the bone: return-into-libc without function calls (on x86)” and “On the expressiveness of return-into-libc attacks” .
• Pokemon Yellow : “The full Pokemon Yellow control hack” describes a memory corruption attack that allows you to create arbitrary programs on Game Boy assembler by walking back and forth and buying items in the game. There are similar achievements by fans of speedran (speed passage), but I usually ignore them as “unclean”: for example, you can turn Super Mario World on SNES into an arbitrary game like “Snakes” or “Pong” , but new programs need to be downloaded to additional equipment . In my opinion, this does not allow us to call Super Mario World an “unexpectedly” turing-complete system and differs from other examples in this article. For example, you can exitfrom Super Game Boy to SNES and arbitrary code such as IRC . This is a controversial difference.
  
  • A similar memory corruption problem arises in printffrom POSIX, in options %n, as in other C library functions ( Karlini et al., 2015 ). From here and «интерпретатор printbf-Brainfuck'sprintf .
  • The StarCraft community has exploited a buffer overflow in the game to implement complex maps, defense games, Mario games, and level editors for it. Hacking emulation to protect mods in updated versions of SC caused Blizzard a lot of problems .
• Braid game is turing complete
• A musical notation with instructions for transferring subsequent notes becomes the esoteric language of Choon .
• The muscle cells of the heart (cardiomyocyte) interact in such a way that they can be programmed through logic gates, therefore, they represent a turing-complete system (perhaps this is not too surprising, because cellular automata are created using a biological example)
• One category of strange machines is not considered completely Turing-complete, because the user must click the mechanical switch or make the only possible choice for the system to go to the next step. In this case, the user does not introduce any logic and does not perform calculations, therefore, this category does not fully satisfy the definition of Turing-complete systems:
  
  • Magic: the Gathering : this is a turing-complete system , based on the assumption that players mechanically agree to the proposed option, but otherwise all actions obey the rules of the game
  • CSS is designed as a declarative markup language for customizing the visual appearance of HTML pages, but elementary cellular automaton Rule 110 , which changes state by mechanical mouse clicks in the browser, can be encoded on CSS declarations
  • Microsoft PowerPoint animations (excluding macros, VBScript, etc.) with special links can implement a Turing machine ( Wildenhain, 2017 : video ; PPT ) if the user clicks on active animation triggers

Perhaps the following systems will accidentally be turing complete:

• CSS without clicks
• SVG: PostScript is TC by design, but what about the more modern SVG vector graphic format , which is written in XML, that is, in a document language that is (usually) not Turing-complete? It seems that in combination with XSLT it may still be so, but I have not found any evidence or demonstration of this in the usual context of a web browser. The SVG standard is great and sometimes terrifying: an unsuccessful version of the SVG 1.2 standard tried to add the ability to open network sockets in SVG images .
• Unicode : Nicholas Seriot suggests that bidirectional Unicode algorithms (designed to display right-to-left scripts, such as Arabic or Hebrew) can be complex enough to support a tag system via case- sensitive rules (e.g., Turkish)

see also

• Intra-platform effect

References

• Discussion at HN: 1 , 2
• Accidentally quadratic
• "Coding machines" ; “Reflections on the Delegation of Trust,” Ken Thompson, 1984
• “Adversarial reprogramming of neural networks” , Elsayed et al., 2018

application

How many computers are in your computer?

Some get bogged down in disputes about strange cars or about how “big” an AI agent will become: one such, two, ten, or millions will be created. It doesn’t matter, since this is just an organizational matter. Actually, the inputs and outputs of the system are important: how efficient is the system as a whole and what resources does it consume? No one cares if Google runs on 50 supercomputers, 50,000 mainframes, 5 million servers, 50 million embedded / mobile processors, or a combination of all of the above . It doesn’t matter that Google uses a variety of chips: from home-made “tensor processors” to unique silicon processors (Intel implements them on chips for Xeon processors for a number of major customers), FPGA, GPU, CPU, to even more exotic equipment like D-Wave quantum computers. It is only important that it remains competitive and can provide services for a moderate fee. In the end, today a supercomputer usually looks like a large number of rack servers with a huge amount of GPUs and unusually high-speed InfiniBand connections. That is, the supercomputer is not so different from the data center, as you might think. Any of the listed equipment can support numerous strange machines, depending on its internal dynamics and connectivity.

Similarly, any AI system can be implemented in the form of one giant neural network or many separate neural networks operating asynchronously, or as a heterogeneous set of microservices, or as a “society of the mind” and so on. All this is not particularly important. From the point of view of complexity or risks, it is not so important how the system is organized while it is working. The system can be seen at many levels, each of which is equally invalid in itself, but is useful for different purposes in the general system.

Here is an example of a poorly defined question: how many computers do you have in your pockets and on your desk now? How many computers are in your “computer”? Think only one? Let's take a closer look.

It's not just about the CPU: nowadays, transistors and processor cores are so cheap that now it often makes sense to allocate separate cores for real-time tasks, to improve performance, for security, to avoid loading the main OS, for compatibility with the old architecture or existing software package. Just because a DSP or kernel is faster to program than creating a specialized ASIC, or because it is the simplest solution possible. In addition, many of these components can be used as computational elements, even if they are not intended or even hide this functionality.

So:

• In a conventional Intel processor, billions of transistors perform many tasks:
  
  
  • Each of the 2-8 main processor cores is able to work independently, turning on and off as necessary, it has its own cache (larger than RAM in most computers until recently), and it should be considered as an independent computer.
  • The CPU as a whole is reprogrammed via microcode, for example, to eliminate chip design errors, and flaunts increasingly opaque objects, such as Intel Management Engine (with JVM for programming ; Rouen, 2014 and SGX ) or AMD's Platform Security Processor (PSP), or TEE All Android . These hardware modules, as a rule, are full-fledged computers in their own right, work independently of the host, and may interfere with its operation.
  • Any FPU can become a Turing-complete system through encoding in floating point operations in the spirit of FRACTRAN.
• The MMU can be programmed into a strange page-fault machine, as mentioned above.
• DSP blocks , custom chips. Probably, ASICs for video formats like h.264 will not be turing-complete systems (despite the support of complex deltas and compression methods that can allow something like Van tiles). But here's the Apple A9 mobile SoCgoes far beyond a conventional dual-core ARM processor with an integrated GPU. Like Intel or AMD desktop chips, it includes a secure environment called Secure Enclave (physically allocated processor cores), but it also contains a coprocessor for images, a coprocessor for voice recognition (partially to support Siri), and, apparently, several other cores. These ASICs sometimes exist for AI tasks and, apparently, specialize in matrix multiplications for neural networks, and since recurrent neural networks are Turing complete, then ... you understand. Motorola, Qualcomm and other companies also rushed to expand their SoC.
• Motherboard BIOS and / or network access control chips.
  
  
  • Mark Ermolov notes:
    
    

    “It's amazing how many heterogeneous processor cores are integrated into Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, each with its own firmware and support for the JTAG interface

  
  These control or debugging chips can “accidentally” remain activated on devices after sale, like the built-in ARM in the Via C3 CPU .
• The GPU has several hundred or thousands of simple cores, each of which works very well with neural networks or performs general-purpose calculations (albeit slower than a processor).
• Tape, hard drive, flash drive, and SSD controllers typically run on ARM processors to run built-in utilities for tasks such as hiding bad sectors from the operating system. They can be hacked. But ARM processors are used in most embedded applications, so ARM loves to boast that “a modern smartphone contains from 8 to 14 ARM processors, one of which is an application processor (running Android or iOS), and the other is a processor for the frequency band stack (baseband stack) . "
• network chips perform independent processing for DMA (thanks to such independence functions like Wake-on-LAN for netboot work ).
• smartphones: in addition to all the blocks mentioned, there is also an independent baseband processor that runs under its own real-time OS to process communications with cell towers / GPS / etc. Or even more than one if you use virtualization like L4 . Backdoors have already been detected in baseband processors, in addition to other vulnerabilities.
• SIM cards for smartphones are much more than just memory cards with the recording of your subscriber data. These are smart cards that can independently run Java Card applications (probably NFC chips too). It's like a JVM in IME. Naturally, SIM cards can be hacked and used for surveillance, etc.
• Devices connected via USB or to the motherboard can be equipped with their own processors. For example, WiFi adapters, keyboards, mice, etc. Theoretically, most of them are isolated from direct interference with the host through DMA and IOMMU, but the devil is in the details ...
• random weird chips like the MacBook Touch running WatchOS .
• ...

So in a regular smartphone or desktop computer there will be from fifteen to several thousand computers in the sense of turing-complete devices. Each of them can be programmed, it has sufficient power to run many programs and can be used by an attacker to monitor, exfiltrate or attack the rest of the system.

There is nothing unusual in the historical context, because even the very first mainframes usually included several computers, where the main computer performs batch processing, and auxiliary computers provide high-speed I / O operations, which otherwise would interfere with the main machine with their interrupts.

In practice, in addition to the information security community (since all these computers are unsafe and, therefore, useful for NSA and virus writers), all other users do not care that under the hood of our computers are insanely complex systems that are more accurately regarded as a motley menagerie of hundreds computers embarrassingly connected with each other (it is not clear, “a network is a computer” or “a computer is a network” ...?). The user perceives and uses this as one computer.

---

1. An active area of ​​research is the creation of languages ​​and systems that are carefully designed and guaranteed not to be Turing-complete (for example, totally functional programming ). Why put so much effort into creating a language that many programs cannot write? The fact is that Turing completeness is closely related to Gödel’s incompleteness theorem and Rice’s theorem.. Therefore, if TC is allowed, then we lose all possible provability properties. On the contrary, various useful things are easily proved in a Turing incomplete language: for example, that a program is complete, type-safe or not, that it is easy to convert to a logical theorem, that it consumes a limited amount of resources, that the protocol implementation is true or equivalent to another implementation. It is easy to prove that there are no side effects and that the program can be converted to a logically equivalent, but faster option (this is especially important for declarative languages ​​like SQL, where the optimizer’s ability to convert queries is the key to acceptable performance. Although, of course, amazing things can be done with SQL, such as thegradient descent for machine learning models , and some SQL extensions make it turing complete anyway, allowing you to either encode a loop system , or modelDSL , or call PL / SQL , etc.

Here is some literature on weird cars:

• “Exploit Programming: From Buffer Overflows to Weird Machines and Computation Theory” , Bratus et al., 2011
• “The Stop Problem in Network Stack Security,” Sassamen et al., 2011
• The Strange Page-Fault Machine: Lessons in Computing Without Instructions , Bangert et al., 2013
• “Strange cars at ELF: a focus on underestimated metadata,” Shapiro et al 2013
• “Interrupt-oriented programming of bugs: a minimalistic approach to introducing bugs in firmware of embedded systems” , Tan et al., 2014
• Strange Cars in the Evidence-Based Code , Vaneg, 2014
• “Cyclical Signals — Returning to Portable Shellcode,” Bosman and Bos, 2014

↑

2. Although linear neural networks exploit the floating point mode with rounding to zero to encode potentially Turing-complete behavior (for RNN), it is invisible in normal operation, which is also a random Turing-complete behavior and a good example of a safe language. ↑

3. Dwarf Fortress provides clockwork, so Turing completeness is not surprising. But water is also implemented as a simple cellular automaton, so there are even more ways to get turing completeness! Now, the game wiki names four potential ways to create logic gates: liquids, clockwork mechanisms, mine carts and creature / animal logic gates with doors and pressure sensors. ↑

4. The full PDF specification is exceptionally bloated. For example, in a simple PDF viewer that supports enough of the PDF specification, like the Google Chrome browser, you can play Breakout (because PDF includes its own weird subset of JavaScript). The official Adobe PDF viewer supports functionality up to three-dimensional CAD. ↑

5. See the domino logic gates on Think Math and the demo of a 4-bit domino knuckle adder . ↑