114 min listen
288: Turing Complete Sed
FromBSD Now
ratings:
Length:
59 minutes
Released:
Mar 7, 2019
Format:
Podcast episode
Description
Software will never fix Spectre-type bugs, a proof that sed is Turing complete, managed jails using Bastille, new version of netdata, using grep with /dev/null, using GMail with mutt, and more.
##Headlines
###Google: Software is never going to be able to fix Spectre-type bugs
Spectre is here to stay: An analysis of side-channels and speculative execution
Researchers from Google investigating the scope and impact of the Spectre attack have published a paper asserting that Spectre-like vulnerabilities are likely to be a continued feature of processors and, further, that software-based techniques for protecting against them will impose a high performance cost. And whatever the cost, the researchers continue, the software will be inadequate—some Spectre flaws don’t appear to have any effective software-based defense. As such, Spectre is going to be a continued feature of the computing landscape, with no straightforward resolution.
The discovery and development of the Meltdown and Spectre attacks was undoubtedly the big security story of 2018. First revealed last January, new variants and related discoveries were made throughout the rest of the year. Both attacks rely on discrepancies between the theoretical architectural behavior of a processor—the documented behavior that programmers depend on and write their programs against—and the real behavior of implementations.
Specifically, modern processors all perform speculative execution; they make assumptions about, for example, a value being read from memory or whether an if condition is true or false, and they allow their execution to run ahead based on these assumptions. If the assumptions are correct, the speculated results are kept; if it isn’t, the speculated results are discarded and the processor redoes the calculation. Speculative execution is not an architectural feature of the processor; it’s a feature of implementations, and so it’s supposed to be entirely invisible to running programs. When the processor discards the bad speculation, it should be as if the speculation never even happened.
###A proof that Unix utility sed is Turing complete
Many people are surprised when they hear that sed is Turing complete. How come a text filtering program is Turing complete, they wonder. Turns out sed is a tiny assembly language that has a comparison operation, a branching operation and a temporary buffer. These operations make sed Turing complete.
I first learned about this from Christophe Blaess. His proof is by construction – he wrote a Turing machine in sed (download turing.sed). As any programming language that can implement a Turing machine is Turing complete we must conclude that sed is also Turing complete.
Christophe offers his own introduction to Turing machines and a description of how his sed implementation works in his article Implementation of a Turing Machine as a sed Script.
Christophe isn’t the first person to realize that sed is almost a general purpose programming language. People have written tetris, sokoban and many other programs in sed. Take a look at these:
Tetris
Sokoban (game)
Calculator
##News Roundup
Bastille helps you quickly create and manage FreeBSD Jails.
Bastille helps you quickly create and manage FreeBSD Jails.
Jails are extremely lightweight containers that provide a full-featured UNIX-like operating system inside. These containers can be used for software development, rapid testing, and secure production Internet services.
Bastille provides an interface to create, manage and destroy these secure virtualized environments.
Current version: 0.3.20190204-beta.
Shell Script Source here: https://github.com/BastilleBSD/bastille/blob/master/usr/local/bin/bastille
###netdata v1.12 released
Netdata is distributed, real-time, performance and health monitoring for systems and applications. It is a highly optimized monitoring agent you install on all your systems and containers.
Netdata provides unparalleled insights, in real-time, of everythin
##Headlines
###Google: Software is never going to be able to fix Spectre-type bugs
Spectre is here to stay: An analysis of side-channels and speculative execution
Researchers from Google investigating the scope and impact of the Spectre attack have published a paper asserting that Spectre-like vulnerabilities are likely to be a continued feature of processors and, further, that software-based techniques for protecting against them will impose a high performance cost. And whatever the cost, the researchers continue, the software will be inadequate—some Spectre flaws don’t appear to have any effective software-based defense. As such, Spectre is going to be a continued feature of the computing landscape, with no straightforward resolution.
The discovery and development of the Meltdown and Spectre attacks was undoubtedly the big security story of 2018. First revealed last January, new variants and related discoveries were made throughout the rest of the year. Both attacks rely on discrepancies between the theoretical architectural behavior of a processor—the documented behavior that programmers depend on and write their programs against—and the real behavior of implementations.
Specifically, modern processors all perform speculative execution; they make assumptions about, for example, a value being read from memory or whether an if condition is true or false, and they allow their execution to run ahead based on these assumptions. If the assumptions are correct, the speculated results are kept; if it isn’t, the speculated results are discarded and the processor redoes the calculation. Speculative execution is not an architectural feature of the processor; it’s a feature of implementations, and so it’s supposed to be entirely invisible to running programs. When the processor discards the bad speculation, it should be as if the speculation never even happened.
###A proof that Unix utility sed is Turing complete
Many people are surprised when they hear that sed is Turing complete. How come a text filtering program is Turing complete, they wonder. Turns out sed is a tiny assembly language that has a comparison operation, a branching operation and a temporary buffer. These operations make sed Turing complete.
I first learned about this from Christophe Blaess. His proof is by construction – he wrote a Turing machine in sed (download turing.sed). As any programming language that can implement a Turing machine is Turing complete we must conclude that sed is also Turing complete.
Christophe offers his own introduction to Turing machines and a description of how his sed implementation works in his article Implementation of a Turing Machine as a sed Script.
Christophe isn’t the first person to realize that sed is almost a general purpose programming language. People have written tetris, sokoban and many other programs in sed. Take a look at these:
Tetris
Sokoban (game)
Calculator
##News Roundup
Bastille helps you quickly create and manage FreeBSD Jails.
Bastille helps you quickly create and manage FreeBSD Jails.
Jails are extremely lightweight containers that provide a full-featured UNIX-like operating system inside. These containers can be used for software development, rapid testing, and secure production Internet services.
Bastille provides an interface to create, manage and destroy these secure virtualized environments.
Current version: 0.3.20190204-beta.
Shell Script Source here: https://github.com/BastilleBSD/bastille/blob/master/usr/local/bin/bastille
###netdata v1.12 released
Netdata is distributed, real-time, performance and health monitoring for systems and applications. It is a highly optimized monitoring agent you install on all your systems and containers.
Netdata provides unparalleled insights, in real-time, of everythin
Released:
Mar 7, 2019
Format:
Podcast episode
Titles in the series (100)
1: BGP & BSD: We kick off the first episode with the latest BSD news, show you how to avoid intrusion detection systems and talk to Peter Hessler about BGP spam blacklists! by BSD Now