As you may remember, during a good 15 years, every OpenBSD release came with one or sometimes a few songs or musical pieces. If you have been enjoying these songs, you might remember a line, near the beginning of the 5.7 song, ``Source fish'', which says: ``Got the Propolice in the GCC''.
Come to think of it, while old-timers will immediately recognize what the lyrics are referring to, the name ``Propolice'' has slowly fallen into oblivion, and I wouldn't be surprised if many people, nowadays, do not have a clue about this.
Allow me to fill the gaps.
Behold, the story of Propolice.
Our story starts in 1998. The dotcom Internet bubble is at its early stages. At this years' Usenix technical conference, a team of fresh graduates from the Oregon Institute of Science and Technology, led by Crispin Cowan, present StackGuard, a compiler patch (against gcc 2.7.2.2, back then), which is designed to mitigate control flow attacks causing the return address on stack to be overwritten.
This hardened code generation is used to build a variant of the already popular Red Hat Linux distribution, called Immunix.
This presentation unfortunately mostly falls on deaf ears, Immunix remaining a niche distribution. These deaf ears include the gcc developers, even though the StackGuard changes soon get ported to the (much more reactive) egcs project, which will eventually take over gcc development as of gcc 2.95 in 1999.
One of the reasons for the lack of interest may be the non-portability of the gcc patch. Quoting from the Usenix paper: ``The changes are architecture-specific (in our case, i386), but since the total changes are under 100 lines of gcc, portability is not a major concern.''
Enters Hiroaki Etoh. Working in the IBM Technical Research Labs in Japan, he decides to write his own version of the StackGuard patch, but in a portable way. In addition to introducing a similar checked value on the stack, his diff also reorders local variables of functions to put the non-array variables at lower stack addresses, to also prevent them from being overwritten by a stack buffer overflow.
The entirety of the Propolice code lies in the machine-independent parts of the compiler, unlike StackGuard. It operates on the compiler's internal representation of the code (RTL), and as such is expected to work on all hardware platforms supported by gcc. However, being placed in a more generic code area, and with the extra logic to reorder local variables, the patch is much larger than StackGuard; the core of the changes are put in a new protector.c file, which is over 2,000 lines (including comments).
A paper describing this work is published in june 2000 by Hiroaki Etoh and Kunikau Yoda.
A few months later, Hioraki Etoh sends his diff to the gcc-patches mailing list, where (surprise!) it falls on deaf ears, maybe because it is based on egcs 1.1.2, which is a bit old. His mail mentions the Propolice web page as well.
The next month, he sends an updated diff, first targeting the latest public gcc snapshot, then targeting the up-to-date gcc, version 2.95. The feedback is mostly negative, gcc developers preferring the work on compile-time bounds checking, and the patch, much larger than StackGuard, is considered too intrusive to be worth considering.
Nevertheless, Hiroaki Etoh does not give up and keeps maintaining his patch, porting it to gcc 3.0 in june 2001, and also making work on 32-bit sparc systems running Solaris, to prove the portability of his approach. The Propolice web page is updated to reflect this.
The next year, on april 23rd, 2002, security researcher Gera Richarte from CORE-SDI in Argentina publishes a few ways to bypass the stack smashing protection. All existing technologies are affected... but Propolice.
Later this year, in june, the OpenBSD project releases a few security errata for OpenBSD 3.1 (and 3.0), and, disgruntled by these, starts switching its mindset from ``our work is to make the code bug-free'' to ``in addition to making the code bug-free, we should make exploitation as difficult as possible''. One of these first changes is to make the stack no longer executable on platforms where this can be done thanks to MMUs managing separate read and execute permissions. While thinking about stacks, one of the OpenBSD developers, Federico G. Schwindt, remembers StackGuard and discovers Hiroaki Etoh's work.
After giving it a successful run on an OpenBSD/i386 system, he sends a mail to Theo de Raadt, the OpenBSD project leader, to start a discussion about this. Theo tells him to involve more people, and that's how a mail with subject ``propolice diffs for gcc'' ends up in my mailbox (and a few other developers) on july 4th.
I become immediately enthusiastic about the promises of Propolice; but if we want to make use of it in OpenBSD, it needs to work on all our supported platforms, which at that time span 7 processor families: alpha, i386, m68k, PowerPC, sparc (both 32-bit and 64-bit) and vax. In 2002, amd64 (or x86_64 if you prefer this ugly name) does not exist yet outside of AMD labs, arm and mips won't come back to OpenBSD until a few years, and neither the PA-Risc port (hppa) nor the m88k support are in working condition at that time.
One of the first systems I tried Propolice on was a venerable HP 9000/425t, a 25MHz 68040-based workstation running OpenBSD/hp300 (I did not yet have faster 68060 systems yet at this point). Unfortunately, the experiment would turn short quite quickly, when the Propolice-enabled compiler would fail to recompile itself, one of the intermediate programs used to produce backend-specific data (genattr) would always hit a segmentation fault and dump core.
Tinkering with the coredump and the `genattr` code, I was able to produce a simple reproducer on july 23rd:
Date: Tue, 23 Jul 2002 09:35:21 +0000
From: Miod Vallat
To: Federico Schwindt, Theo de Raadt
Subject: Propolice failure on m68k
/*
Propolice fails on m68K when you use alloca() in a routine, and then
invoke a subroutine that has enough local variables.
Here is a simple test program that exhibits the problem. It causes a
core dump on m68k at any optimization level (well, I only tested -O0 and
-O2) on m68K with your Propolice diffs applied to gcc. If you remove the
spacefiller variable inside the subroutine, it will work nicely. Same if
you trim the char[] variable down to 7 bytes (final \0 included in
count) or less.
Does it affect other arches too?
If it only affects m68K, I guess it would be easier to look at how
alloca() works on this arch and alter it so that it can coexist with
propolice.
Miod
*/
#include <stdlib.h>
int
depth(i)
int i;
{
char spacefiller[] = "1234567"; /* "123456" will pass */
return (i);
}
int
main()
{
char *data;
data = alloca(42);
return (depth(42));
}
Not being able to make progress from that (my knowledge of gcc internals was simply nonexistent in these days), we decided to get Hiroaki Etoh involved and asked him whether he would be willing to help us. Fortunately, he was, and an account for him was setup on my personal lab on the 24th:
Date: Wed, 24 Jul 2002 07:41:24 +0000 From: Miod Vallat To: Hiroaki Etoh Cc: Federico Schwindt Subject: Account on an m68k machine Hello, I have setup your account on my net. Access by ssh to "gentiane.org" first, then from the machine you arrive on, "ssh -1 epi" will let you reach a fast (for an m68k) hp300 machine. Please use ssh -1 there to save cpu pover... The compiler here is OpenBSD's gcc with your propolice changes, You can also use the regular, non propolice, compiler, should that be necessary, with "gcc -V2.95.3-NP". If you need anything, ask fgs or myself. Regards, Miod
Later that day, Theo sent a mail to Hiroaki Etoh explaining what our (OpenBSD) plans with regard to Propolice were:
Date: Wed, 24 Jul 2002 02:49:15 -0600 From: Theo de Raadt To: etoh@jp.ibm.com Subject: propolice i really hope we can get this stuff into the tree for all our architectures. but it must be for all, before it goes in -- disabled at first. then once it works on all, we will enable it for certain parts. all this must happen VERY fast for it to make our next release. it is unlikely we can enable it for the entire tree by next release, unless you and fgs work very hard at it... miod is a very good person to help as well for testing --- his ethics in that sense are out of control. however, the schedule does kind of suck, time is getting tight... there is a 2 month window to get it utterly completely working on all arch's... that is m68k, sparc, sparc64, alpha, i386, powerpc, vax [hppa and m88k do not matter yet] [...] anyways, talk to you soon. if you get m68k working, we can get you access to other architectures. like vax. vax will be fun ;-) i have a vax that is faster than a top of the line sparc 20, so it is not to be mocked.
It took Hiroaki Etoh some time to get started, as he was not used to the OpenBSD source tree (although he had some experience with FreeBSD) and expected to be able to work in a way similar to Linux distributions, extracting a tarball of the official gcc sources and configuring it for the current system. I had to explain that the OpenBSD source repository contains a copy of the compiler sources, with some patches, not all of them having been accepted (or even submitted) upstream, and that he had to work on this tree in order to build a working OpenBSD compiler.
Once he had understood how to rebuild the compiler, things progressed quite fast. The Propolice patch, back then, did not expect (and did not cope with) the m68k pre-decrement and post-increment addressing modes used on the stack pointer. Because of this, it would end up miscomputing stack pointer-relative offsets, and then generate incorrect code.
Once the Propolice patch was made aware of these addressing modes, things went a bit further, but trying to compile part of the gcc support code (libgcc2.a) would end up with mysterious errors from the assembler:
rm -f tmplibgcc2.a
for name in _muldi3 _divdi3 _moddi3 _udivdi3 _umoddi3 _negdi2 _lshrdi3 _ashldi3
_ashrdi3 _ffsdi2 _udiv_w_sdiv _udivmoddi4 _cmpdi2 _ucmpdi2 _floatdidf _floatdi
sf _fixunsdfsi _fixunssfsi _fixunsdfdi _fixdfdi _fixunssfdi _fixsfdi _fixxfdi _
fixunsxfdi _floatdixf _fixunsxfsi _fixtfdi _fixunstfdi _floatditf __gcc_bcmp _v
arargs __dummy _eprintf _bb _shtab _clear_cache _trampoline __main _exit _ctor
s _pure _guard; do echo ${name}; ./xgcc -B/usr/m68k-unknown-openbsd3.1/bin/ -
B./ -I/usr/m68k-unknown-openbsd3.1/include -O2 -DIN_GCC -O2 -O2 -save-tem
ps -DOPENBSD_NATIVE -I./include -g1 -DIN_LIBGCC2 -D__GCC_FLOAT_NOT_NEEDED -fp
ic -I. -I/usr/src/gnu/egcs/gcc -I/usr/src/gnu/egcs/gcc/config -I/usr/src/gnu/egc
s/gcc/../include -c -DL${name} -DUSE_COLLECT2 /usr/src/gnu/egcs/gcc/libgcc2.c -o
${name}.o; if [ $? -eq 0 ] ; then true; else exit 1; fi; ar rc tmplibgcc2.a $
{name}.o; rm -f ${name}.o; done
_muldi3
_divdi3
_moddi3
_udivdi3
_umoddi3
_negdi2
_lshrdi3
_ashldi3
_ashrdi3
_ffsdi2
_udiv_w_sdiv
_udivmoddi4
_cmpdi2
_ucmpdi2
_floatdidf
_floatdisf
_fixunsdfsi
_fixunssfsi
libgcc2.s: Assembler messages:
libgcc2.s:120: Error: cannot create floating-point number
libgcc2.s:127: Error: cannot create floating-point number
*** Error code 1
I asked Hiroaki Etoh again for help. It turns out that there was an endianness bug in his code deciding how to setup local variables on stack in some circumstances, and floating-point types larger than the register size ended up laid out in little-endian order, which was obviously not going to work on m68k, which is a big-endian architecture.
At the end of july, the Propolice-enabled compiler would pass the gcc regression testsuite as badly as the non-Propolice compiler (a large majority of the tests would pass, and those which did fail were already failing without the Propolice changes, so it was not to blame for these failures).
But the road was still not clear, as at the same time Matthieu Herrb started to test on PowerPC and quickly found that the Propolice-compiler built libc did not behave correctly either. He was able to narrow this to a libc file which had to be built with optimization disabled (or with Propolice disabled).
At that time, we also noticed that two developer OpenBSD accounts had been compromised in june, and I spent quite some time on forensics, as well as checking all the ssh connection logs over the last few months, and check with everyone whether the IP their connections originated from were legitimate. This temporarily distracted me from testing Propolice or doing any other OpenBSD-related work.
Nevertheless, by the middle of august, Propolice on m68k was considered stable, being able to rebuild itself, and build the complete OpenBSD/hp300 userland.
It was time to try another untested architecture: vax (my plans were to test the slowest platforms first, as any regression there would take time to get fixed and the fix to be validated).
Date: Mon, 2 Sep 2002 08:40:20 +0000 From: Miod Vallat To: Hiroaki Etoh Subject: vax You can now login to "durolle". /usr/src only contains the gnu/egcs/gcc subdirectory, with unpatched sources. Feel free to play with it - I'll use another similar vax to build a complete system with propolice in a few moments. Miod
While Hiroaki Etoh was confronting his code to the Vax challenge (a CISC processor with many complex addressing modes, and a hardware controlled stack frame layout) on that middle-end, 55MHz VAXstation 4000/60, it was time to work on tieing the loose ends and making a first candidate patch against the OpenBSD tree, and getting more people involved in testing and/or reviewing.
The plan was still to ship a Propolice-capable compiler in the upcoming 3.2 release, and maybe enable the stack protector on a few critical binaries, such as sshd.
With the release cutoff getting close, on september 27, it was decided that Propolice would not be included in the upcoming release, but in the next one.
[=Sign-on=] etoh (etoh@[32.97.110.75]) entered group
<deraadt> hi etoh
<deraadt> the tree will unlock in about two weeks, and then we can make headway
at getting propolice into the tree for real
<deraadt> then in 6 months you can see a complete operating system ship with
your code activated
<deraadt> all our major cpu now work with it? powerpc i386 sparc sparc64 vax
m68k ?
<etoh> I don't have an experience on sparc64 only.
<deraadt> you mean only sparc64 is unconfirmed?
<etoh> yes.
<deraadt> that's cool.
<etoh> Do you have sparc64 machine in miod lab?
<deraadt> i think he's not around.
Three days later, Hiroaki Etoh acknowledged that his patch still needed some changes to run on 64-bit platforms:
[=Sign-on=] etoh (etoh@[32.97.110.75]) entered group
<deraadt> hi
<etoh> hi
<deraadt> so you need sparc64 access now, eh?
<etoh> i can access sparc64 machine in miod's lab. i found that propolice does
not work well on 64 bit machine.
<etoh> i understand the problem, so i'll modify some code.
<deraadt> oh, so alpha has a few issues too?
<deraadt> sparc64 is big-endian 64 bit. this creates quite a few different
types of bugs than a little-endian 64 bit arch does.
<etoh> the problem comes from the size of frame pointer register, not endian.
<etoh> i understood there is no alpha system in openbsd platform, right?
<jason> ? We run on alphas...
<t> what? alpha works. well, mine doesn't....
<etoh> all right. so, i have to test alpha too.
After a few changes to Propolice, a first, incomplete, patch integrating Propolice into the OpenBSD tree was shared among developers on october 8th:
Date: Tue, 8 Oct 2002 22:18:55 +0000 From: Miod Vallat To: private mailing list Subject: propolice meets the tree, step 1 The following diff puts the current version of propolice into the tree. For those who missed the story, propolice is a stack attacks protection built into the compiler, so that, if some flaw in the code results in stack corruption, the program abort rather than continuing and possibly running an exploit. More details at http://www.trl.ibm.com/projects/security/ssp This diff adds propolice to our gcc, but does not enable it by default. To explicitely compile something with propolice, use the -fstack-protector option. To explicitely compile something without propolice, use the -fno-stack-protector option. So far, this version of propolice is known to work correctly on: - i386 - m68k - sparc - vax and to not work on: - alpha (being worked on) - sparc64 (being worked on) Powerpc did not work last time checked, but numerous problems have been fixed since and it's worth another try. Ok, now before it sounds like I did all the work, propolice was first spotted by fgsch@, who did the necessary OpenBSD modifications to the libgcc changes. Hiroaki Etoh, the author, did the m68k and vax fixes, and is working on more. I only behaved as a test loony. [...] If you are interested in building complete systems with propolice enabled, don't do that out of the box. fgs and I have diffs to apply to various parts of the tree (especially ld.so) to make this work. You have been warned. [...]
A second patch, this time complete, was shared on november 22nd:
Date: Fri, 22 Nov 2002 00:35:49 +0000 From: Miod Vallat To: private mailing list Cc: Hiroaki Etoh Subject: Propolice meets the OpenBSD tree, part 2 This new diff brings -again- the latest propolice code into the main OpenBSD tree. The diffs against the previous diff are: - propolice is disabled by default. Use cc -fstack-protector to benefit of the code. This will eventually be turned on for more and more parts of the system. - the stack smash handler attempts to log information about what happened. This won't work on chroot binaries unless /dev/log exists in the chroot jail, though, but there's no easy way to solve this. - a.out and ELF ld.so diffs to be able to compile with propolice, even if some code is dummied. - sys/ hooks to always disable propolice. You can change this to enable propolice in the kernel, but this will be over my dead, cold, body. Tested on almost all arches (means, I have tested different versions of this diff but it should be ok now). [...] I would really like this to go in the tree ASAP, as even with propolice disabled, this affects gcc behaviour. Then we can enable protection after some time, the goal being that 3.3 ships with propolice enabled at least on the most sensitive parts of the system. [...] Known problems with stack protection so far: - emacs port will not link. I'm working on a fix, but don't push me, it's emacs we are talking about. - I have got some mitigated results with perl 5.8, builds fine on some arches, not as well on others, I'll need to have a closer look. Fixed problems include 64 bit support, inline functions, and everything fgs, naddy and I don't remember. Send flames to me, technical questions to etoh with me and fgs cc'ed. Miod
The patch was however not final as we were still tinkering with the __stack_smash_handler routine, which gets invoked upon function exit when the stack canary value has been modified. In the original Propolice diff, that function was added to the gcc runtime, libgcc.a; but since it would use a few functions from libc to report the stack corruption and exit, this put an unexpected dependency on libc, while libgcc is supposed to be the last library on the linker commandline, and not depend upon anything.
That extra dependency had required us to add explicit libc dependency in several Makefile, for the few daemons we intended to compile with stack protection, which were statically linked, such as isakmpd(8).
Eventually its location in OpenBSD was reconsidered, and it was moved to libc. The body of the __guard_setup function, which is used to compute the canary value upon startup, was also modified to use sysctl to get randomness, rather than reading from /dev/urandom, which may not exist if running within a chroot'ed environment.
With that settled, a new diff was shared on november 29th, and since noone had any further changes to request, the Propolice patch landed in OpenBSD on december 2nd, enabled by default on all platforms.
Unfortunately (and predictibly), it was not long until we found the hard way that some problems had managed to creep in.
Date: Tue, 3 Dec 2002 07:52:30 +0000 From: Miod Vallat To: private mailing list Subject: First propolice in-tree problem... It turns out there are issues with gnu bc again on alpha. Etoh has been notified. [...]
I was quite surprised that I had missed this during all my tests, so I investigated a bit, found why I had missed it, and shared an explanation:
Date: Tue, 3 Dec 2002 21:14:30 +0000 From: Miod Vallat To: private mailing list Subject: dc bug story I found a workaround for the propolice problems in gnu/usr.bin/dc, as well as the reason why it was not found earlier. It turns out that make cleandir does not remove the generated fbc helper utility. Hence I was happily building with an old compiled, thus working, fbc binary. I only get bitten by the problem when I wiped my /usr/obj tree. As for the workaround, I tracked the problem to be in bc.c - only this file needed to be compiled with -O0 with propolice for fbc to work. It turns out this is a generated file, from bc.y, via bison. Unfortunately it uses some gnuisms, so our in-tree flex can not process it. Using the port of bison, I generated a new bc.c, fixed bc.h to make the constants match again, and it built like a charm. Very simple tests show no difference of behaviour. [...]
Jason Downs was quick to point that I should process the bc.y file with yacc, not flex (doh!), and that was enough to get a working bc binary.
Further analysis showed that the old generated parser for bc used alloca() while the newly recompiled one didn't. Hiroaki Etoh quickly came with a simple fix to handle that situation anyway, and no changes in build machinery were needed after all.
The Propolice web page was updated to mention these recent achievements.
A few more bug fixes were added in the next few months (two or three per month), and then OpenBSD 3.3 was released with all userland binaries, as well as the binary packages for third-party software, compiled with stack protection, on all platforms... but OpenBSD/hppa.
Indeed, in early 2003, the OpenBSD/hppa porting effort made significant progress and that port become a reality. However, one of the (many) odd things about the PA-RISC architecture, is that the stack is architectured to grow up (towards larger addresses), unlike all other platforms.
When I mentioned this to Hiroaki Etoh, he was quick to realize there was no way to achieve a working stack protection:
From: Hiroaki Etoh
Date: Fri, 10 Jan 2003 11:21:01 +0900
To: Miod Vallat
Subject: Re: "make build" policy, and a few other notes
[...]
< The main thing to know about hppa, is that the stack grows up, contrary
< to most other platforms, and this is probably where propolice has
< issues.
oh my god.
Do you know that propolice can not protect the following on the processor?
void bar (char *p) {
gets(p); /* buffer overflow */
}
int foo () {
char buf[20];
bar (buf);
}
In this case, the overflow damages the frame region of "bar", it means the
return address in it can be compromised.
To avoid this situation, we can put a canary on top of the stack and check
the integrity of the canary every time before a function call. BUT it is
a great overhead.
[...]
The only reasonable choice to make was to keep Propolice disabled on hppa.
After the OpenBSD 3.3 release, other software projects (especially Linux distributions, starting with Gentoo) followed the OpenBSD example and started to add Propolice to their system compiler and enable it on key software.
Occasional problems and fixes continued until shortly before the OpenBSD 3.6 release, with a last bug exposed by the mysql testsuite.
Eventually, as part of changes in gcc 4 to rewrite, in a cleaner way, the code responsible to setup call frames, a "smoother" reimplementation of the protection, in much fewer lines of code, was created in 2005: This proposal got refined a few weeks later. This time, there were no objections to it, and it got merged shortly afterwards; gcc 4.1, released in february 2006, was the first release with the feature available.
After that, Hiroaki Etoh no longer had to work on his patch. The latest patches he published were for gcc 3.3 and 3.4. And then he went on to work on other projects.
Consequently, the Propolice page on IBM's web site received no updates after august 2005, was moved to http://www.research.ibm.com/trl/projects/security/ssp/ in december 2011, before eventually disappearing in july 2014. You can visit the last available version archived by the wayback machine.
After all these years, the name Propolice had disappeared.
But its work is done, and its legacy is there - in this day and age, cheap stack protection and smart local variable reordering are available in all serious compilers, and the computing world is a (slightly) safer place because of it.