Sign up to save your podcasts
Or
Share Turing Complete Sed | BSD Now 288
Share to email
Share to Facebook
Share to X
Share to email
Share to Facebook
Share to X
Or
Turing Complete Sed | BSD Now 288
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
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:
##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.
###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 everything happening on the systems it runs (including web servers, databases, applications), using highly interactive web dashboards. It can run autonomously, without any third party components, or it can be integrated to existing monitoring tool chains (Prometheus, Graphite, OpenTSDB, Kafka, Grafana, etc).
Netdata is fast and efficient, designed to permanently run on all systems (physical & virtual servers, containers, IoT devices), without disrupting their core function.
###Using grep with /dev/null, an old Unix trick
Every so often I will find myself writing a grep invocation like this:
find .... -exec grep /dev/null '{}' '+'
The peculiar presence of /dev/null here is an old Unix trick that is designed to force grep to always print out file names, even if your find only matches one file, by always insuring that grep has at least two files as arguments. You can wind up wanting to do the same thing with a direct use of grep if you’re not certain how many files your wildcard may match.
###USING GMAIL WITH MUTT
I recently switched to using mutt for email and while setting up mutt to use imap is pretty straightforward, this tutorial will also document some advanced concepts such as encrypting your account password and sending emails from a different From address.
This tutorial assumes that you have some familiarity with using mutt and have installed it with sidebar support (sudo apt-get install mutt-patched for the ubuntu folks) and are comfortable with editing your muttrc.
If you would just like to skip to the end, my mutt configuration file can be found here.
##Beastie Bits
##Feedback/Questions
Your browser does not support the HTML5 video tag.
View all episodes
By Allan Jude
4.9
1919 ratings
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
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:
##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.
###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 everything happening on the systems it runs (including web servers, databases, applications), using highly interactive web dashboards. It can run autonomously, without any third party components, or it can be integrated to existing monitoring tool chains (Prometheus, Graphite, OpenTSDB, Kafka, Grafana, etc).
Netdata is fast and efficient, designed to permanently run on all systems (physical & virtual servers, containers, IoT devices), without disrupting their core function.
###Using grep with /dev/null, an old Unix trick
Every so often I will find myself writing a grep invocation like this:
find .... -exec grep /dev/null '{}' '+'
The peculiar presence of /dev/null here is an old Unix trick that is designed to force grep to always print out file names, even if your find only matches one file, by always insuring that grep has at least two files as arguments. You can wind up wanting to do the same thing with a direct use of grep if you’re not certain how many files your wildcard may match.
###USING GMAIL WITH MUTT
I recently switched to using mutt for email and while setting up mutt to use imap is pretty straightforward, this tutorial will also document some advanced concepts such as encrypting your account password and sending emails from a different From address.
This tutorial assumes that you have some familiarity with using mutt and have installed it with sidebar support (sudo apt-get install mutt-patched for the ubuntu folks) and are comfortable with editing your muttrc.
If you would just like to skip to the end, my mutt configuration file can be found here.
##Beastie Bits
##Feedback/Questions
Your browser does not support the HTML5 video tag.