LWN.net Weekly Edition for February 24, 2022

Welcome to the LWN.net Weekly Edition for February 24, 2022

This edition contains the following feature content:

• Python support for regular expressions: what is to be done about Python's outdated re module?
• Moving Python's bugs to GitHub: the last step in Python's move is a big one.
• A last look at the 4.4 stable series: what happened over six years of stable-kernel maintenance.
• Thoughts on software-defined silicon: Linux will support Intel's "software-defined silicon" mechanism, but users may not be thankful.
• Shadow stacks for user space: some challenges remain before this security mechanism will be ready for use.

This week's edition also includes these inner pages:

• Brief items: Brief news items from throughout the community.
• Announcements: Newsletters, conferences, security updates, patches, and more.

Please enjoy this week's edition, and, as always, thank you for supporting LWN.net.

Comments (1 posted)

Python support for regular expressions

Regular expressions are a common feature of computer languages, especially higher-level languages like Ruby, Perl, Python, and others, for doing fairly sophisticated text-pattern matching. Some languages, including Perl, incorporate regular expressions into the language itself, while others have classes or libraries that come with the language installation. Python's standard library has the re module, which provides facilities for working with regular expressions; as a recent discussion on the python-ideas mailing shows, though, that module has somewhat fallen by the wayside in recent times.

Timeouts?

J.B. Langston posted to the list on February 14; he had filed a bug about a problem he encountered using re, which was closed with a suggestion that he bring it to the mailing list. Langston had a regular expression (which is often abbreviated as "regex" or "regexp") that seemed to hang his program when applied to a rarely occurring log message; it turned out that there was a flaw in his regular expression, which caused an enormous amount of backtracking that, effectively, never completed. In the bug report, he was asking for a way to specify a timeout:

I will try to rewrite my regex to address this specific issue, but it's hard to anticipate every possible input and craft a bulletproof regex, so something like this kind of thing can be used for a denial of service attack (intentional or not). In this case the regex was used in an automated import process and caused the process to back up for many hours before someone noticed. Maybe a solution could be to add a timeout option to the regex engine so it will give up and throw an exception if the regex executes for longer than the configured timeout.

He elaborated his use case further in his post:

My use case is log parsing and I have a large number of regexes that run over many different log lines. With the volume of regexes I have, it's hard to make sure every regex has no potential problems, especially when the pathological behavior only occurs on certain inputs that may not have been anticipated when developing the regex.

Also because of the volume of data these regexes are parsing, I would never want to allow a regex to run longer than a few milliseconds because if it did, that would kill my log processing throughput. I'd rather that it just raise an exception and move on to the next log entry.

Jonathan Slenders replied that the regex module on the Python Package Index (PyPI) has support for timeouts. regex is meant to be both a drop-in replacement for re (using its "version 0") and to provide support for additional regular-expression features when using "version 1". Those features include nested sets, full Unicode case-folding by default, dropping the global interpreter lock (GIL) during matching for concurrency, and more. The regex home page lists a whole raft of differences when using version 1, including a timeout parameter for the matching functions.

Musings on regular expressions

Tim Peters also mentioned regex, though not because it implements timeouts (which is something he only learned via the thread), but because it is "a terrific module" with many features from newer regular-expression implementations. It is "also harder to provoke into exponential-time bad cases". He discussed some of the tradeoffs that come with regular expressions and recommended the classic book, Mastering Regular Expressions, for those struggling to use them well. He noted that SNOBOL, which is a string-processing language from the 1960s, did not have regular expressions, though there were tasks where it (and its successor of sorts, Icon) were able to do matching in more natural ways:

Naive regexps are both clumsy and prone to bad timing in many tasks that "should be" very easy to express. For example, "now match up to the next occurrence of 'X'". In SNOBOL and Icon, that's trivial. 75% of regexp users will write ".*X", with scant understanding that it may match waaaay more than they intended. Another 20% will write ".*?X", with scant understanding that may extend beyond _just_ "the next" X in some cases. That leaves the happy 5% who write "[^X]*X", which finally says what they intended from the start.

Those who are not well-versed in regular-expression syntax may find some of that a bit puzzling. While this article cannot be an introduction to regular expressions—there are countless web sites, books, and other resources for that—we will try to give readers a bit of a leg up. In regular-expression syntax, "." represents any single character, adding "*" says to match zero or more occurrences of the previous term, so ".*" matches any string, while ".*X" matches any string up to a literal "X". But, as the following example shows, that may not be exactly what the programmer had in mind:

    >>> import re
    >>> re.search(r'.*X', 'abcXdefXg')
    <re.Match object; span=(0, 8), match='abcXdefX'>

The match value in the object returned from re.search() shows that it matched all the way up to the second occurrence of "X" in the string. That is because the "*" operator is "greedy"—it matches as much as it can. The 20% case in Peters's message uses the non-greedy quantifier "?" to get closer to the result that was asked for:

    >>> re.search(r'.*?X', 'abcXdefXg')
    <re.Match object; span=(0, 4), match='abcX'>

The 5% case, "[^X]*X", uses a negated character set, "[^X]", which means to match anything but "X". So that regular expression can be read as "match any characters that are not 'X', followed by 'X'", but it may well not be the first thing that comes to mind. Steven D'Aprano was surprised that ".*?X" might match beyond the next "X", but Chris Angelico pointed out that non-greedy does not mean it will only match to the next "X":

Nongreedy means it'll prefer the next X, but it has to be open to checking others.

>>> re.search("a.*?X[^X]*?Y", "zzzabbbXcccXdddYzzz")
<re.Match object; span=(3, 16), match='abbbXcccXdddY'>

The X between bbb and ccc won't result in a match, so the .*? has to capture more.

The sub-thread extended a ways, looking into deeper aspects of matching "up to the next 'string'", which shows the complications that can arise—complete with mistaken "solutions". As can be seen, regular expressions are a powerful mechanism, but they are complex, can be used inappropriately, and are prone to bugs of various sorts; they are also difficult to test fully and to debug when problems are encountered. But they have become ubiquitous in today's computing landscape. Peters said:

As to why regexps prevailed, traction! They are useful tools, and _started_ life as pretty simple things, with small, elegant, and efficient implementations Feature creep and "faster! faster! faster!" turned the implementations more into bottomless pits now ;-)

Matthew Barnett ("MRAB"), who is the developer of regex, agreed with that assessment:

Regexes were simple to start with, so only a few metacharacters were needed, the remaining characters being treated as literals.

As new features were added, the existing metacharacters were used in new ways that had been illegal until then in order to remain backwards-compatible.

Add to that that there are multiple implementations with differing (and sometimes only slightly differing) features and behaviours.

It's a good example of evolution: often messy, and resulting in clunky designs.

Back to timeouts and regex

Langston "quite enjoyed reading" the thread that resulted from his post, but wanted to see if there was support "for adding a timeout feature to the Python re library". He said that he would be investigating regex but still thought re could benefit from a way to stop runaway regular expressions. Angelico was opposed to the idea, suggesting that some of the other matching techniques explored in the thread should be pursued instead. "It would add overhead to common cases in order to put a shield around pathological ones, and it's difficult to impossible to usefully define the cutoff." As he noted in his first reply, though, Peters thinks that no work is likely to be done on features for re:

Buried in the fun discussion was my guess: no way. Python's re is effectively dead legacy code, with no current "owner". Its commit history shows very little activity for some years already. Most commits are due to generic "code cleanup" crusades that have nothing specific to do with the algorithms. None required non-trivial knowledge of the implementation.

Peters said that the code that makes up the regex module was originally targeted at becoming part of core Python back in 2008 by its original author, Jeffrey C. Jacobs; the work was picked up and carried forward by Barnett, and eventually turned into regex. The request to switch re over to using it was closed in 2021 because of the existence of regex in PyPI; "If someone wants to move it into the Python stdlib, I suggest to start on the python-ideas list first."

The problem is that regex has "_dozens_ of features that would be valuable to have in the standard library", Peters said, so:

[N]o core dev I know of is going to devote their limited time to reproducing a tiny subset of regex's many improvements in Python's legacy engine. In fact, "install regex!" is such an obvious choice at this point that I wouldn't even give time to just reviewing a patch that added timeouts.

Barnett said that he eventually decided against having the regex code added to the standard library, at least in part because "that would tie fixes and additions to Python's release cycle". Python is known for being "batteries included", "but not nuclear reactors", so having regex in PyPI makes more sense, he said. Peters thought that some features in regex might have been nuclear reactors back in 2008, but are being used more commonly today:

[...] Python's re module is frozen in an ever-receding past. Nobody wants to work on it because, well, "regex already does that! In fact, it's been doing it for 15 years already".

Your module is _too_ successful for Python's good ;-)

Peters also pointed out that trying out regex may be easier than Langston realized. In fact, because of the version 0 compatibility mode, he could perhaps add a simple import to give it a whirl:

    import regex as re

In another message, Peters further described what he meant by that:

What I wrote here is more elaboration on that _trying_ this is easier than they might be thinking: They don't have to, e.g., rewrite their regexps, or invoke different function or method names, or worry that they'll get different results. The packages are highly compatible in syntax and semantics and APIs so long as you stick to the things re does. That in no way suggests they _should_ stick to what re does. It's assuring them that _getting started_ is close to trivial. Their current code should continue to work unchanged, apart from just changing "re" to "regex".

It turns out that Langston's program already uses regex "via some transitive dependency", but he was not impressed with its performance when compared to re. A test data set of 700MB was processed in 77 seconds with re but it took 92 seconds with regex. Peters was "mildly surprised" by that, since: "Most times people report that regex is at least modestly faster than re".

Whither re?

The performance of regex seems like something that might need attention, especially if it is becoming the de facto regular-expression module for Python. Peters's analysis of the status of re is somewhat disheartening; it is apparently permanently stuck in the past. That may be sufficient for many, however, but it somehow seems suboptimal to have two separate pieces of the Python ecosystem that both support the more limited re subset; most enhancements are likely to only go into regex so that re falls further and further behind the state of the art.

Supplanting re with regex in the standard library (using version 0 by default) would seem attractive, though Barnett seems at least somewhat cautious about doing so. A similar thing occurred with the popular Requests HTTP module, which was considered as a possible addition to the standard library at the 2015 Python Language Summit. The conclusion was that it made more sense for Requests to stay out of the standard library because it moves faster than the normal Python release cadence (then 18 months, but now yearly), especially for security updates (which are done more frequently for the language, but not as quickly as Requests can move on its own).

The "batteries included" story for Python has been a major part of its success over the years, but it is starting to fray in various ways. For one thing, the large number of said batteries is straining the maintenance ability of the Python core developers. That has led to discussions, a Python Enhancement Proposal (PEP), and further discussion about removing some parts of the library over the years. Most of the modules in the standard library were added long ago and, once something is added, it is difficult to remove it—even if the reason for its inclusion and the existence of maintainers for it have gone away.

Meanwhile, regular expressions are clearly something that Python programmers use—a lot—so having the best support for them, in one place if possible, seems like the right approach. As Peters noted, they are a "a tool with a hyper-concise notation, where a correct expression is pretty much indistinguishable from line noise, and a typo is rarely detectable as a syntax error". Adding risks of incompatibility (or differing performance) into the mix may not lead to much joy either. It is all a bit of a pickle, but not that pickle, of course.

On the other hand, re, which was originally developed by Fredrik Lundh (who sadly died back in November), does what it needs to do for lots of different use cases. Those who need timeouts, atomic groups, nested character sets, possessive quantifiers, and other advanced features have a place to turn. Barnett seems keen to maintain the compatibility with re, so it may turn out to be a situation, like with Requests, where alternatives to the standard library should be recommended, perhaps even in the Python documentation. There is no clear and obvious "right" solution here it seems.

Comments (28 posted)

Moving Python's bugs to GitHub

Over the past seven years or so, Python has slowly been moving its development infrastructure to GitHub; we covered some of the early discussions at the end of 2014. One piece of that infrastructure, bug tracking, has not been moved from bugs.python.org, but plans are underway to make that happen soon. It is not a simple or straightforward process to do so, however, so the transition will take up to a week to complete; there are a number of interesting facets to the switch, as it entails clearing some technical, and even legal, hurdles.

The plan

Python's developer-in-residence, Łukasz Langa, announced the plan and schedule on the Python Discourse forum on February 18. As described in PEP 581 ("Using GitHub Issues for CPython"), the Roundup-based bugs.python.org (often abbreviated as "bpo" or "BPO") will be retired, but live on in read-only mode so that the existing URLs still work. Each of the entries on BPO will be enhanced with information about where the corresponding issue lives on GitHub; after the transition, all new issues will be added to GitHub.

After the discussions in 2014, the move to GitHub got rolling with PEP 512 ("Migrating from hg.python.org to GitHub"); as the title indicates, it was a move away from the Mercurial-based repositories to Git and GitHub. (Mercurial uses "hg" as its nickname and the name of its main binary, after the Atomic symbol for Mercury.) Brett Cannon, who authored PEP 512 and has been one of the driving forces behind the workflow changes that came with the move to GitHub, reported on the progress of the project at the Python Language Summits in 2016 and in 2017. At the summit in 2018, Mariatta Wijaya proposed switching to GitHub Issues for bug tracking, which resulted in PEP 581; it was approved in 2019 and is coming to fruition now.

As Langa noted, though, there are various difficulties in making the switch:

Unfortunately, this is not an easy task technically, procedurally, or legally, as it involves coordinating with several external actors and solving technical challenges mostly unique to our current circumstances. As a result, while progress was steady, it took a long while to get to this point. I was asked by the Steering Council to take over project management on the migration.

He has been working with CPython developer Ezio Melotti and "our friends on the Github side" to push the task forward. His announcement marked the beginning of a two-week feedback-gathering phase. Then, on March 4, a test migration will be done using 10% of the bugs on BPO; if that is successful, and no show-stopping problems are encountered, the migration will start by making BPO read-only on March 10 and beginning the transfer of everything on March 11.

The migration is estimated to take anywhere from 3 to 7 days, depending on the load on Github.com. This is why we will be performing the bulk of it during the weekend to speed things up.

During that time, no new issues can be opened in either place, but GitHub pull requests (PRs) can be created and used as normal. As issues are migrated from BPO and start showing up at GitHub, which will be ongoing during the process, they can be edited there, "but destructive actions (changing issue titles, editing comment content, deleting comments, removal of labels) are HIGHLY DISCOURAGED". Making those kinds of changes will make it more difficult to audit the completeness of the migration.

There is a contingency plan should things stretch out too long: "In the unlikely case that the migration cannot be completed in 7 days, the Steering Council decided that we would abort it and re-enable BPO again." Further details on the plan, its risks, and possible mitigations for them can be found in a GitHub issue. That issue is part of the gh-migration repository, which is where problems should be reported as part of the feedback process: "You can treat it as exercise in using Github issues 😉". There are also example migrated issues available on GitHub for Python developers and others to examine, as well as documentation updates (coming from this PR).

The main legal question to resolve was whether the Python Software Foundation (PSF) is able to move the user-generated content, with its potentially personally identifiable information (PII), from BPO to GitHub. The steering council and PSF lawyers determined that no user consent was required to do so:

Both BPO and Github are public-facing systems. Users actively placed their information (including PII) in the BPO system, which actively grants consent for that information to be stored, publicly accessible, and distributed on-demand. Changing our backend to Github does not revoke that permission. At the same time, the migration will not be surfacing any new user information that wasn't previously publicly accessible in the BPO system.

Concerns

As might be guessed, one of the concerns expressed in the forum regarded the multi-day pause in the use of the bug tracker. Eric Snow wondered if the older closed and inactive issues could be locked and migrated first. "Assuming the remaining issues would be much fewer than the inactive ones, I'd expect the disruptive part of the migration would be much (proportionally?) shorter." Langa said that the difficulty with doing that is there is no way to disable GitHub Issues during the migration; as soon as some issues are migrated, there would be two trackers in operation, in effect. "The idea to have two issue trackers open at the same time is making me nervous."

In the announcement, Langa noted that Python and GitHub were able to learn from the experience of the LLVM project, which migrated from Bugzilla to GitHub Issues back in December. That migration took 21 days, so the hope is that experience will lead to a smoother (and quicker) transition for Python. Snow said that the estimate of four to seven days "feels like the end of the world" in terms of its impact on core workflow, but, obviously, 21 days is far worse. Melotti said that he has been in contact with LLVM and others:

If I understand correctly the actual transfer eventually took them a couple of days, but it had a few false starts and issues. I've been talking with the project manager of the LLVM project and a few other people that performed similar migrations in the past, so that we could learn from their mistakes and avoid them.

Irit Katriel suggested that post-migration would make for a good time "to review old issues and close them if they are no longer relevant". Langa agreed with that idea, as did Melotti, who added it to the issue tracking notification for BPO users. A notification email of the change will be sent to BPO contributors, listing the issues they have submitted, been assigned, or were following, along with a link to the corresponding new GitHub Issue.

Victor Stinner asked about a related concern; normally an update to a BPO issue will send an email to those people who have added themselves to the "nosy" list for it. He wondered if the update of the BPO entries to add the new GitHub link would generate said emails; "I'm in the nosy list of 885 BPO issues. Should I expect 885 emails [...]?" Melotti sympathized (at least in part because he is on the nosy list for over 4000 entries), but did not directly address whether the BPO change emails would be generated. He did say that he was still hoping to be able to automatically convert the nosy list subscriptions to their GitHub equivalent. Otherwise, active contributors will need to go into each new bug, one by one, and add themselves.

Steve Dower wondered whether it made sense to migrate the closed issues at all. "While there's always some amount of further discussion on closed issues, the vast majority are never going to be touched again. Why recreate them?". But Katriel said that the closed issues still have useful information, which is best kept in one place:

If you want to search closed tickets for some error message, for instance, you want to search in only one place.

There are issues where the problem is not fixed, but the ticket has relevant discussion and workarounds.

The conversation is still ongoing as of this writing, and presumably will be for another week or more. None of the concerns raised so far seem like they will be all that hard to deal with, though it may still be a pretty painful transition, especially for active, longtime contributors. Whether that all gets worked out on the timeline laid out remains to be seen; it would not be a huge shock if the final transition had to be pushed back a time or two. There are quite a number of moving parts that need to be in alignment for this kind of a transition. Hopefully, it all goes off without a hitch—though that may be a tad overoptimistic.

As with Python learning from LLVM's experience, so too can other projects watch this transition with interest. That is one of the strengths of open source and openly developed software; there is much to be learned from the experience of other projects. In fact, the whole transition from self-hosted to GitHub can be found in the Python mailing lists, forum posts, PEPs, and so on; projects thinking about making a switch like that can prepare themselves better by standing on the shoulders of the projects that have gone before.

The switch away from Roundup also largely completes Python's transition of its development infrastructure from open-source, Python-based tools (Mercurial, Roundup) to the proprietary GitHub "software as a service" offering, which is certainly sad in some ways. But Python has always been a fairly pragmatic project—something it seems to have inherited from former benevolent dictator for life Guido van Rossum—and the intent of these moves was geared toward attracting new developers who are familiar with and comfortable using GitHub. Over the last few years, the project does seem to have picked up some steam—and lots of new faces—so it looks like that effort may be paying off. That, too, may be instructive to other projects.

Comments (7 posted)

A last look at the 4.4 stable series

Linus Torvalds released the 4.4 kernel on January 10, 2016 and promptly left the building for the greener fields of 4.5. This kernel was finished from his point of view, but it was just beginning its life in the wider world, and became the first long-term-stable release to be supported for more than two years. Indeed, the 4.4 release became one of the longest-supported and most widely used releases in the history of the kernel project (so far); it was deployed in vast numbers of Android devices, among other places. The final 4.4 stable release took place on February 3, over six years after 4.4 was "finished"; it is time to take a look at what happened to 4.4 in its stable life.

There were 302 stable updates released for 4.4 over the 2,216 days of its supported life — approximately one release per week for the entire six years. Those releases added 18,974 non-merge changesets to that "stable" kernel (about 8.6 patches per day, every day). By virtue of that work, the 4.4 kernel grew by nearly 90,000 lines of code; 72 new source files were added during that time.

Contributing developers

The 4.4 stable series thus looks, in some ways, like another development cycle, but with even more patches. Some of the other numbers are larger as well; the fixes added to 4.4 were contributed by 3,528 developers over those six years, representing just under 500 different employers. Kernel developers may like adding new features but, in the end, almost all of them end up fixing bugs as well. The top bug fixers were:

Top bug fixes in 4.4.x
Developer	Changesets	Pct
Greg Kroah-Hartman	419	2.2%
Eric Dumazet	367	1.9%
Takashi Iwai	345	1.8%
Arnd Bergmann	336	1.8%
Johan Hovold	327	1.7%
Dan Carpenter	288	1.5%
Thomas Gleixner	168	0.9%
Al Viro	121	0.6%
Eric Biggers	118	0.6%
Colin Ian King	108	0.6%
Linus Torvalds	92	0.5%
Geert Uytterhoeven	87	0.5%
Xin Long	86	0.5%
Jan Kara	84	0.4%
Nathan Chancellor	84	0.4%
Alan Stern	82	0.4%
Steven Rostedt (VMware)	82	0.4%
Hans de Goede	81	0.4%
Cong Wang	80	0.4%
Christophe JAILLET	79	0.4%

Note that most of Greg Kroah-Hartman's "fixes" are actually the 302 tags applied to mark each release, leaving 117 actual fixes. The developers involved say a lot about where the bugs show up; Eric Dumazet works in networking and Takashi Iwai is the sound maintainer, for example. Arnd Bergmann, instead, puts a lot of effort into fixing problems all over the kernel tree, as does Dan Carpenter. Johan Hovald works all over the driver tree with a focus on the USB subsystem. It is worth noting that even the most productive contributors of fixes were individually responsible for less than 2% of the total.

A bit of a different story comes out if one looks at testers and reviewers.

Test and review credits in 4.4.x

Tested-by Guenter Roeck 75 3.7% Pavel Machek 57 2.8% Jon Hunter 55 2.7% Linux Kernel Functional Testing 53 2.6% Shuah Khan 50 2.4% Andrey Konovalov 44 2.1% Aaron Brown 44 2.1% Andrew Bowers 38 1.9% Dmitry Vyukov 35 1.7% Arnaldo Carvalho de Melo 27 1.3% Borislav Petkov 21 1.0% Jason Self 17 0.8% Stan Johnson 16 0.8% Joe Lawrence 15 0.7% Marc Zyngier 12 0.6% Jon Masters 12 0.6% Krishneil Singh 12 0.6%

Reviewed-by Greg Kroah-Hartman 112 2.1% David Sterba 109 2.1% Christoph Hellwig 107 2.0% Alexey Makhalov 100 1.9% Matt Helsley 100 1.9% Bo Gan 100 1.9% Hannes Reinecke 80 1.5% Johannes Thumshirn 72 1.4% Borislav Petkov 70 1.3% Jan Kara 70 1.3% Christian König 59 1.1% Nick Desaulniers 57 1.1% Andrew Morton 54 1.0% Andy Shevchenko 54 1.0% Ingo Molnar 52 1.0% Juergen Gross 50 0.9% Eric Dumazet 48 0.9%

Only 1,527 patches applied to 4.4 contained Tested-by tags — that is just 8% of the total. That seems a bit surprising, given that each of those patches is meant to be a fix, so testing whether it works should be relatively straightforward.

The first few lines of the Reviewed-by column are not particularly surprising; both Kroah-Hartman and Christoph Hellwig do a lot of reviews in general, and David Sterba is the Btrfs maintainer. The next few names, Alexey Makhalov, Matt Helsley, and Bo Gan, are a bit more surprising, though; Makhalov and Helsley only have one directly authored patch each in the kernel, while Gan has none. In all three cases, digging through the logs shows a flurry of activity in mid-2018; these three developers, as it turns out, played a big role in the backporting of the Meltdown and Spectre fixes to the 4.4 kernel.

Patch review and selection

There were 4,101 patches applied to 4.4 that contained at least one Reviewed-by tag; that is 22% of the total. Compare that to the 37% of patches going into 5.16 with such tags. One might conclude that patches going into the stable kernels are getting less review than they should, but it is also likely that we are seeing the growth in the use of Reviewed-by tags over time. The fact that only 19% of the patches going into 4.5 had Reviewed-by tags would tend to back up that hypothesis.

How are the bugs fixed in the stable updates found? One clue can be found in the Reported-by tags used to credit bug reporters; 3,529 commits in 4.4.x contained such tags, with the most active reporters being:

Top bug reporters in 4.4.x
Reporter	Reports	Pct
Syzbot	684	17.1%
Dmitry Vyukov	146	3.7%
Hulk Robot	145	3.6%
kernel test robot	88	2.2%
Andrey Konovalov	85	2.1%
Dan Carpenter	69	1.7%
Ben Hutchings	39	1.0%
Jann Horn	31	0.8%
kbuild test robot	30	0.8%
Guenter Roeck	23	0.6%
Al Viro	20	0.5%
Wen Xu	18	0.5%
Linus Torvalds	16	0.4%
Jianlin Shi	16	0.4%
Geert Uytterhoeven	14	0.4%
Julien Grall	14	0.4%
Eric Dumazet	13	0.3%
Tetsuo Handa	13	0.3%
Eric Biggers	13	0.3%
Alexander Potapenko	13	0.3%

Dmitry Vyukov is the developer behind Syzbot, so the first two lines could properly be combined, showing that one developer is responsible for nearly 21% of the credited bug reports leading to 4.4.x fixes — an impressive total. Other automated testing systems added another 6.6% of the reports. Some of the other top reporters are almost certainly using tools of their own to seek out bugs. Every one of these bugs is a problem that was fixed before it was encountered by users, which can only be a good thing.

Also on the topic of tags: maintainers add stable@vger.kernel.org to a patch's CC list to mark a patch as being suitable for stable-kernel updates. Over the course of 4.4.x, 3446 patches (a bit over 18% of the total) were marked in this way. Obviously, the CC list is not the mechanism by which most patches get into the stable updates. In some subsystems (networking in particular), the maintainers manage a separate queue of stable-bound patches and actively discourage developers from marking patches themselves.

Most of the time, though, the patches are being picked by the stable-kernel maintainers themselves, either by hand or through the use of a machine-learning system. This process is frequently controversial. The Fixes: tag is often thought to be the indicator used by the stable team to pick patches that have not been explicitly marked for stable updates. The 4.4.x series included 7,629 patches with such tags, which is still only 40% of the total, so that tag is not a strong indicator either. The stable team is selecting patches that look like fixes even in the lack of any explicit markings.

Regressions and overall conclusion

One interesting use for Fixes: tags, though, is to see whether they refer to other patches that had been included in previous stable releases. In other words, is a patch with a Fixes: tag fixing a bug that was introduced in the stable series itself? Each such occurrence would indicate a regression shipped in a stable update, which is exactly what the stable kernels are meant to avoid.

Over the course of the 4.4 stable series, 1,309 patches contained Fixes: tags referring to commits appearing earlier in the stable series. Of those, though, 310 fixed patches that had been merged for the same stable update; those bugs never made it through to a release, and thus should not be counted as regressions. Some patches required multiple fixes and should not be counted twice; filtering those out leaves 884 patches — 4.7% of the total — that added regressions to the stable updates. Many of these regressions were likely never noticed by users, of course, but a few of them were serious.

Through all of this, the 4.4 kernels drove a huge number of devices. It was an allowed kernel version for the Android 7 through 9 releases, and is, without doubt, still running on a lot of devices despite the end of ongoing support. Many millions of people have benefited from the work that the stable-kernel maintainers (and all of the people who have helped them) have done. Assigning a dollar value to this work would be difficult, but the resulting number would have to be huge; it is a significant gift to the world as a whole.

The free-software community has often shown that it is better at cranking out software than supporting that software over long periods of time; the latter task often falls to providers who expect to be paid for access to their work. The 4.4.x kernel has shown, though, that the kernel community is, when it sets its mind to the task, indeed able to provide support for a full six years. The stable team's approach to picking patches is controversial, and probably will always be regardless of how the policy evolves, but the results were clearly good enough to build an extended ecosystem around. It is hard to conclude that this effort was anything but a significant success.

Comments (8 posted)

Thoughts on software-defined silicon

People are attracted to free software for a number of reasons, including price, overall quality, community support, and available features. But, for many of us, the value of free software is to be found in its ability to allow us to actually own and maintain control over our systems. Antifeatures in free software tend not to last long, and free drivers can often unlock capabilities of the hardware that its vendors may not have seen fit to make available. Intel's upcoming "software defined silicon" (SDSi) mechanism may reduce that control, though, by taking away access to hardware features from anybody who has not paid the requisite fees.

SDSi is a "feature" that is expected to make an appearance in upcoming Intel processors. Its purpose is to disable access to specific processor capabilities in the absence of a certificate from Intel saying otherwise. As the enabling patch set from David Box makes clear, the interface to the mechanism itself is relatively simple. It appears as a device on the bus that offers a couple of operations: install an "authentication key certificate" or a "capability activation payload". The certificate is used to authenticate any requests to enable features, while the payload contains the requests themselves. Unless this device has been used to store an acceptable certificate and payload, the features that it governs will be unavailable to software running on that CPU.

The SDSi hardware also maintains a couple of counters that track the number of unsuccessful attempts that have been made to load a certificate or enable a feature. Should either counter exceed a threshold, the mechanism will be disabled entirely; the only way to get it back will be to power-cycle the processor. Presumably, the intent here is to thwart attempted brute-force attacks against the SDSi gatekeeper.

Intel is clear enough about the purpose behind this new mechanism. SDSi will enable shipping CPUs with features that may be of interest to users, but which are unavailable unless additional payments are made. The restricted capabilities will be present on all shipped CPUs, but the customers, who might have thought that they own their expensive processors, will not be able to use their systems to their fullest capability without add-on (and perhaps recurring) payments to the vendor.

The benefits to Intel are clear. The company can do price differentiation among its customers in an attempt to extract the maximum revenue from each while simultaneously reducing the number of different hardware products it must carry in its catalog. The revenue stream from a processor will not necessarily stop once the CPU is purchased, and might continue indefinitely. The benefit for customers is not quite so clear. In theory, customers with minimal needs can avoid paying for expensive features they don't use and can "upgrade" their hardware without downtime if their needs change.

Also unclear is which features Intel intends to control in this manner. One can imagine all kinds of things, including the ability to access larger amounts of memory, higher clock rates, additional CPUs, specialized instructions, or accelerators for workloads like machine learning. Taken to its extreme (which the company would presumably not do, though one never knows anymore), an off-the-shelf processor might be unable to run anything more demanding than "hello world" until additional licenses have been purchased. There was a time when a floating-point processor was an add-on unit; perhaps we will find ourselves there again.

This business model is not new, of course; stories abound regarding early mainframes that could be "upgraded" by altering a single jumper. Tesla automobiles include a number of features, including basic capabilities like use of the full capacity of the battery, that only work if an extra payment is made; there is no shortage of reports that the company will disable those features when one of its cars is resold. Car manufacturers evidently want to extend this idea to, for example, requiring subscription payments to enable heated seats. The heating elements exist in the seats regardless, and the manufacturer sold them to the buyer, but the buyer still does not really own them.

Rent-based business models have been spreading through the technology industry for some time. Many of us no longer purchase and run our own servers; we rent them from a cloud provider (and, to the tell the truth, are often better off for it). Companies that are still in the proprietary software business are finding the monthly subscription model more appealing than simply selling software licenses. And, of course, there are dodgy web sites out there demanding payments for access to their content.

But the problem seems worse for hardware that has been purchased, and which the customer, on the theory that they own said hardware, may believe they can rightly use to its fullest capability. Our free software, which is supposed to enable that use, finds itself relegated to asking the hardware for permission to use the available features. It is a loss of control over our systems, yet another set of secrets hidden away inside our computing hardware and protected by anti-circumvention laws; if this approach is commercially successful, we will surely see much more of it.

It is hard to see a way out of this situation that doesn't involve making hardware free in the same way that we have done with software. Maybe someday it will be possible to order the fabrication of processors from free designs and at least be able to hope that the result will be lacking in deliberate antifeatures. But that is not the world we live in now, and it's not clear that we will get there anytime soon.

Meanwhile, SDSi is definitely coming to Linux; maintainer Hans de Goede has indicated that this work is on track to be merged for 5.18. There are not a whole lot of arguments that can be made against the acceptance of the SDSi driver; it simply enables another piece of functionality packaged with upcoming CPUs. The kernel community has not made a practice of judging whether it likes the "features" provided by a specific peripheral before accepting driver support, and it would be hard to justify starting now. So the Linux kernel will play along with SDSi-enabled CPUs just fine; it will be up to customers to decide whether they want to be as agreeable.

Comments (103 posted)

Shadow stacks for user space

The call stack is a favorite target for attackers attempting to compromise a running process; if an attacker finds a way to overwrite a return address on the stack, they can redirect control to code of their choosing, leading to a situation best described as "game over". As a result, a great deal of effort has gone into protecting the stack. One technique that offers promise is a shadow stack; support for shadow stacks is thus duly showing up in various processors. Support for protecting user-space applications with shadow stacks is taking a bit longer; it is currently under discussion within the kernel community, but adding this feature is trickier than one might think. Among other things, these patches have been around for long enough that they have developed some backward-compatibility problems of their own.

Shadow-stack basics

Whenever one function calls another, information for the called function, including any parameters and the address to which the function should return once it has done its work, is pushed onto the call stack. As the call chain deepens, the chain of return addresses on the stack grows apace. Normally, all works as intended, but any corruption of the stack can cause one or more return addresses to be overwritten; that, in turn, will cause execution to "return" to an unintended location. With luck, that will cause the application to crash; if the corrupt data was deliberately placed there, instead, execution could continue in a way that will cause worse things to happen.

Shadow stacks seek to mitigate this problem by creating a second copy of the stack that (usually) only contains the return-address data. Whenever a function is called, the return address is pushed onto both the regular stack and the shadow stack. When that function returns, the return addresses are popped off both stacks and compared; if they fail to match, the system goes into red alert and (probably) kills the process involved. Shadow stacks can be implemented entirely in software; even if the shadow stack is writable, it raises the bar for an attacker, who must now be able to corrupt two areas of memory, one of which is at an arbitrary location. Hardware support can make shadow stacks stronger, though.

Intel processors, among others, can provide that support. If a shadow stack has been set up (which is a privileged operation), the pushing of return addresses onto that stack and comparison on function return are all done by the CPU itself. Meanwhile, the shadow stack is normally not writable by the application (other than by way of the function-call and return instructions), and thus not corruptible by an attacker. The hardware also requires the presence of a special "restore token" on the shadow stack itself that, among other things, ensures that two processes cannot be sharing the same shadow stack — a situation that, once again, would facilitate attacks.

Supporting user-space shadow stacks

The current version of the shadow-stack support patches has been posted by Rick Edgecombe; the bulk of the patches themselves were written by Yu-cheng Yu, who has posted numerous earlier versions of this work. Enabling this feature requires 35 non-trivial patches, and the problem is not entirely solved yet. One might wonder why it is so hard, since shadow stacks seem like a feature that most code could ignore almost all of the time, but life is never so simple.

As might be expected, the kernel must contain the code to manage user-space shadow stacks. That includes enabling the feature at the processor level, and handing it for each specific process. Each process needs its own shadow stack set up with a proper restore token, then the (privileged) shadow-stack pointer register must be aimed at it. Faults, both normal page faults and things like integrity-violation traps, must be handled. There is yet more information to be managed on context switches. This is all pretty normal stuff for a new feature of this sort.

The memory allocated for the shadow stack itself must be treated specially. It belongs to user space, but user-space code must not normally be allowed to write to it. The processor must also recognize memory dedicated to shadow stacks, so they must be marked specially in the page tables, and that's where things get a little interesting. There are a number of bits set aside in each page-table entry (PTE) to describe the protections that apply and various other types of status, but the x86 architecture does not include a "this is a shadow-stack page" bit. There are some PTE bits set aside for the operating system's use; Linux does not use them all and could have spared one for this purpose, but evidently certain other operating systems have no spare PTE bits, so stealing one for this purpose would not be welcome.

The solution that the hardware engineers arrived at might well be described as a bit of a hack. If a page's write-enable bit is clear (indicating that it cannot be written to), but its dirty bit is set (indicating that it has been written to), the CPU will conclude that the page in question is part of a shadow stack. This is a combination of settings that, in ordinary usage, might not make sense, so it evidently seemed like fair game.

Unfortunately, Linux kernel developers came to a similar conclusion many years ago, so Linux has its own interpretation for that combination of PTE bits. Specifically, that is how the kernel marks copy-on-write pages. The lack of write access will cause a trap should a process attempt to write the page; the presence of the dirty bit then tells the kernel to make a copy of the page and give the process write access to it. It all works well — until the CPU comes along and applies its own interpretation to that bit combination. So much of the patch set is focused on grabbing one of those unused PTE bits for a new _PAGE_COW flag and causing the memory-management code to use it.

Shadow stacks bring other complications as well, of course. If a process calls clone(), a new shadow stack must be allocated for the child process; the kernel handles this task automatically. Signals, as always, add complications of their own, since they already involve various stack manipulations. It gets worse if a process has set up an alternative stack for signal handlers with sigaltstack() — to the point that the current patch set does not handle that case at all. From such details (and more), a long patch series is made.

ABI issues

The use of shadow stacks should be entirely transparent to most applications; after all, developers rarely think about the call stack in any case. But there will always be applications that do tricky things with their stacks, starting with multi-threaded programs that explicitly manage the stack area for each thread. Others may place their own specially crafted thunks onto the stack or even more obscure things. Without special care, all of those applications will break if they are suddenly set up with a shadow stack. That sort of mass regression tends to make security features unpopular, so various measures have been taken to avoid it.

The carefully considered plan that emerged was to mark applications (with a special property in the .note.gnu.property ELF section) that are prepared to run with a shadow stack. Applications that do no stack trickery could simply be rebuilt and run with shadow stacks thereafter. For the more complicated cases, a set of arch_prctl() operations was defined to enable the explicit manipulation of shadow stacks. The GNU C Library was enhanced to use these calls to configure the environment properly on application startup, and the kernel would enable shadow stacks whenever a suitably marked program was run. Some distributions, including Fedora and Ubuntu, have been building their binaries for shadow stacks; all they need is a suitably equipped kernel to run with the extra protection.

It is always dangerous to ship code using kernel features that have not yet been accepted and merged; shadow stacks turn out to be an example of why. According to the cover letter on the current series, the arch_prctl() API was "abandoned for being strange". But those shadow-stack-ready binaries deployed on systems worldwide were built expecting that API, strange or not, to be present; if the kernel respects the markings in the ELF file and enables shadow stacks for those programs, some of them will break. That would cause system administrators worldwide to disable shadow stacks until at least 2040, rather defeating the purpose of the whole exercise.

One obvious workaround for this problem would be to never recognize the current ELF marker for shadow stacks and, instead, create a new one to mark binaries using the interface actually supported by the kernel. The decision that was made, though, was to get the kernel out of the business of recognizing shadow-stack-capable binaries entirely and let the C library take care of it. So, if this version of the ABI is adopted, the kernel will never enable shadow stacks unless user space requests it.

The proposed interface

Overall control of shadow stack functionality is to be had with a (presumably not strange) arch_prctl() call:

    status = arch_prctl(ARCH_X86_FEATURE_ENABLE, ARCH_X86_FEATURE_SHSTK);

There is also an ARCH_X86_FEATURE_DISABLE operation that can be used to turn shadow stacks off, and ARCH_X86_FEATURE_LOCK to prevent future changes.

While most applications need not worry about shadow stacks, some of them will need to be able to create new ones. Applications using makecontext() and friends are a prominent example. Creating a shadow stack requires kernel support; the associated memory must have the special page bits set as described above, and must also include the restore token. So there is a new system call for this operation:

    void *map_shadow_stack(unsigned long size, unsigned int flags);

The size of the desired stack is passed as size, while flags has a single possibility: SHADOW_STACK_SET_TOKEN to request that a restore token be stored in the stack. The return value on success is the address of the base of this stack.

Actually using this new stack is a matter of executing the RSTORSSP instruction to make the switch, most likely done as a part of a user-space context switch between threads. That instruction will perform the necessary verification of page permissions and the restore token before making the switch. It will also mark the token on the new shadow stack as being busy, preventing that stack from being used by any other process.

Applications doing especially tricky things may require the ability to write to the shadow stack. That access is normally not allowed for obvious reasons but, as Edgecombe noted, that "restricts any potential apps that may want to do exotic things at the expense of a little security". For the exotic case, another feature (LINUX_X86_FEATURE_WRSS) can be turned on with arch_prctl(); that, in turn, enables the WRSS instruction, which can write to shadow-stack memory. Directly writing to that memory by dereferencing a pointer is still disallowed in this case.

What next?

This work is not exactly new; an early version of it was covered in this 2018 article. In its previous incarnation, the shadow-stack patch set got up to version 30. The other half of the control-flow integrity work (indirect branch tracking), which got up to version 29 itself, has been set aside for the moment (though Peter Zijlstra has just shown up with a separate implementation). With a new developer heading up the work, a reduction in scope, and some asked-for changes, it is hoped, this work can finally make some progress toward the mainline.

In a number of ways, it looks like that hope might be realized. While there were comments on various parts of the patch set, there does not appear to be a lot of opposition to how it works at this point. Developers did express concern, though, about the lack of support for alternate signal stacks. That is a feature that seems certain to be wanted at some point, so it would be good to see how it fits into the whole picture before this functionality is merged.

There was also a separate subthread regarding problems with Checkpoint/restore in user space (CRIU), which engages in no end of underhanded tricks to get its job done. One part of the checkpoint process involves injecting "parasite" code into a process to be checkpointed, grabbing the needed information, then doing a special return out of the parasite to resume normal execution. That is just the sort of control-flow tampering that shadow stacks are meant to prevent. Various possible solutions were discussed, but nothing has appeared in code form at this point. A solution here, too, seems necessary before shadow stacks can be merged; as Thomas Gleixner put it: "We can't break CRIU systems with a kernel upgrade".

Finally, the range of supported hardware will almost certainly need to be expanded. Some AMD CPUs implement shadow stacks, evidently in a compatible manner, but only Intel CPUs are supported in this patch set; a lack of testing is cited as the reason. That, at least, will probably need to change for the work to go forward. Shadow stacks are also unsupported on 32-bit systems; fixing that may be harder and it is not clear whether the motivation to do that work exists. With or without 32-bit support, though, there is clearly still work to be done before this code enters the mainline. It should not be expected to show up in a near-future release.

Comments (21 posted)