Discover this podcast and so much more

Podcasts are free to enjoy without a subscription. We also offer ebooks, audiobooks, and so much more for just $11.99/month.

288: Turing Complete Sed

288: Turing Complete Sed

FromBSD Now


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
Released:
Mar 7, 2019
Format:
Podcast episode

Titles in the series (100)

Created by three guys who love BSD, we cover the latest news and have an extensive series of tutorials, as well as interviews with various people from all areas of the BSD community. It also serves as a platform for support and questions. We love and advocate FreeBSD, OpenBSD, NetBSD, DragonFlyBSD and TrueOS. Our show aims to be helpful and informative for new users that want to learn about them, but still be entertaining for the people who are already pros. The show airs on Wednesdays at 2:00PM (US Eastern time) and the edited version is usually up the following day.