Leading items

Welcome to the LWN.net Weekly Edition for February 8, 2018

This edition contains the following feature content:

• A cyborg's journey: Karen Sandler updates the linux.conf.au crowd on her quest for the source code for her defibrillator.
• Open-source drug discovery: an attempt to apply open-source principles and techniques to the secretive process of discovering new drugs.
• F-Droid: an alternative to Google Play: how this alternative Android app store works.
• 4.16 Merge window part 1: what was in the first 6,700 changesets merged for the 4.16 development cycle.
• Meltdown and Spectre mitigations — a February update: the current state of kernel mitigations for these vulnerabilities.
• Mixed-criticality support in seL4: a microkernel operating system that claims to be suitable for the most safety-critical settings.
• Jupyter: notebooks for education and collaboration: an overview of the increasingly popular Jupyter environment.

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 (none posted)

A cyborg's journey

Karen Sandler has been giving conference talks about free software and open medical devices for the better part of a decade at this point. LWN briefly covered a 2010 LinuxCon talk and a 2012 linux.conf.au (LCA) talk; her talk at LCA 2012 was her first full-length keynote, she said. In this year's edition, she reviewed her history (including her love for LCA based in part on that 2012 visit) and gave an update on the status of the source code for the device she has implanted on her heart.

Sandler is the executive director of the Software Freedom Conservancy (SFC); she is also a lawyer, but "I do all of my legal work for good now", she said with a chuckle. She does pro bono work for FSF and the GNOME Foundation, for example. She asked how many in the audience had attended LCA 2012 in Ballarat, which turned out to be around one-third (interestingly, the number of first-time attendees was nearly the same).

Ballarat

In the 2012 keynote, she said that she literally has a big heart—three times the size of a normal person's heart. She was diagnosed with this when she was 31 and it meant that she had a 2-3% chance per year of just suddenly dying from a heart malfunction. That led her to get a pacemaker/defibrillator implanted in her heart; it is there to shock her heart if it ever goes into a dangerous rhythm.

When she was preparing to have the device implanted, though, she started asking questions of her doctor about the software that ran on the device. That was something of a culture clash since the doctor had implanted thousands of these devices and no one had ever asked about the software. She was nervous about becoming a cyborg and definitely was not comfortable with having proprietary software in her body.

That event changed the course of her career, Sandler said, because it led her to research software and to realize that free software, over time, has a chance to fix the bugs that all software has. She spoke about all of that in her Ballarat keynote, but she was incredibly nervous because she was not used to talking about her medical problems in front of so many people. However the LCA community "was so supportive"; she believes that particular talk "made my career". To this day she calculates the dates of other major life events by using that keynote as the epoch.

That talk helped people understand why she is passionate about free software; it also helped them grasp why software freedom is important. Without free software, we won't have control over our critical technology. Her story causes the audience to feel vulnerable, which makes it easy to extend the idea beyond medical devices to, say, cars. It is a way to get the message across in a way that most people can relate to; she likes to think of it as "a great printer story".

Since she gave that talk, people would come up and ask her whether she had ever been able to get the source code for her device. The second most popular question was about how it felt to be shocked, she said with a grin. She had asked everyone she could think of for their help in getting the source code and was willing to sign a non-disclosure agreement (NDA) with the device maker, but it didn't go anywhere. She felt helpless and frustrated when people asked about it.

Cyborg

So she channeled her energy elsewhere, into SFC and trying to "create an environment where software freedom can flourish". Her defibrillator is just one example of why it is important. She calls herself a "cyborg" in a "somewhat cheeky way", but we are all in the process of becoming cyborgs or at least knowing others who are. The definition of "cyborg" is "incorporating technology into your body", which covers a lot of ground. The line is rather blurry and could potentially incorporate things like language (a kind of technology) or devices as prosaic as glasses.

SFC is a charity that provides an organizational home for 46 different free and open-source software projects. She specifically pointed to Homebrew, which is under the SFC umbrella, to the many Mac-using attendees. "It is a starting point and next year you will be using GNU/Linux", she said to applause. Beyond that, SFC oversees the Outreachy diversity program that provides internships for people from groups that are traditionally under-represented in the tech world. SFC also represents a coalition of Linux kernel developers to enforce the GPL; it does the same service for its member projects.

Meanwhile, though: "Hey, did you ever get the source code to that thing in your heart?", she said, returning to the theme (and part of the title) of her talk. After failing to get the source code, she started networking with members of the security and medical device communities. She participated in getting a DMCA exemption so that researchers could study and report on security problems in medical devices. Before that exemption, it was potentially a criminal act (in the US at least) to test the safety of your own device. And, as she said in Ballarat, these devices are the worst of both worlds: they have software that no one can review and they are doing wireless communication with little or no security. The DMCA exemption was a concrete result from her efforts, which was gratifying.

At the same time, however, there were more and more published vulnerabilities against medical devices. When she first started advocating for free software on these devices (or at least to be able to review the code under an NDA), "people looked at me like I had two heads". One electro-physiologist called her a "conspiracy theorist" for saying that these kinds of devices had vulnerabilities. She made the mistake of pointing out that many of those who have these devices are older politicians and that, if someone wanted to do a mass attack on them, she (and others) might be collateral damage. The doctor said he would help, but thought there was something wrong with her. She is now on electro-physiologist number five, she said with a chuckle.

But once these vulnerabilities became more public and the medical device makers started taking security a bit more seriously, it was easier to talk with doctors and others about the problem. She mentioned several high-profile vulnerabilities like the flaws reported by investment firm Muddy Waters in St. Jude Medical cardiac implants; Muddy Waters drew attention to the problems by short-selling St. Jude stock. By way of contrast, Johnson & Johnson alerted its customers to a vulnerability in its insulin pumps; the company hired one of the security researchers she has worked with to fix those vulnerabilities and get those fixes out to users.

Another set of vulnerabilities came from Barnaby Jack, who is famous for "jackpotting" ATM machines; his flair for presentation helped popularize pacemaker and defibrillator vulnerabilities to the point they started ending up as part of the plots of television shows. Once that happened, she said, it brought the problem to the attention of more people and "lit up the pacemaker forums".

She had written an academic paper on the subject in 2010, but did not mention that she was someone who had an implanted device. When she posted it anonymously to the pacemaker forums, people there claimed that the authors were just trying to scare people who had these devices, since they didn't know what it was like to have to rely on them. She adamantly did not want people to know that she had a medical condition, but she started to realize that she would need to start personalizing the problem, which eventually led to the talk in Ballarat. In addition, Jack emailed her to say that he had seen one of her talks, which caused him to focus on medical devices—an outcome that helped further raise awareness.

After the vulnerabilities made it onto TV, it was much easier to talk to representatives of the medical device makers, for example. Even lawyers were now paying attention, so the in-house counsel for these manufacturers were much more willing to talk with her. It became clear that things had changed and that the device makers were rethinking their risks; in part, they were worried that a judge would see studies showing that free and open-source software is better and safer, which might affect judgments and the like.

Life

She thought she had everything figured out, that things were moving in the right direction, and that she was basically done. She felt like her story was not going to change, she just needed to repeat it; her relationship with her medical device was not going to change. But, then, "life happened"; she got pregnant and at one point was anxious (about the future of free software, actually, she said sheepishly). That led to her getting shocked by her defibrillator—twice. She went to the emergency room and the doctors were completely "freaked out". It turns out that doctors do not want a pregnant woman to get shocked even once.

That made for a great time to advocate for software freedom, Sandler said with a laugh. She talked to around 40 doctors that night about software freedom. It is normal for pregnant women to have heart palpitations that would trigger the device—25% do—but the subset of pregnant women that have a defibrillator is tiny. Most are implanted in those over 65 and less than half are for women. In the tests of her device, 18% of the subjects were women and none were pregnant. That makes sense, but her needs were not met.

Medical professionals did not want her getting shocked and neither did the device makers. They would like to fix the problem, but it stems from a temporary condition that is relatively hard to test for. In her case, her doctors gave her drugs to slow her heart down—to the point she could barely walk up a flight of stairs—in order to stop her device from shocking her.

She started to wonder about other things in her life that may not have been anticipated by her device maker. There is no ill will involved, she said; if the device maker could have incorporated her pregnancy parameters into the device, it would have, but pregnancy just wasn't on their radar. What other factors play into the functioning of our software that may not be anticipated by its makers? Maybe the user is not in the geographic area that was planned for, not speaking a language that is supported, or is not in the anticipated age range. She could have this device for 15 years or more and she was not filled with confidence that changes over that time are properly being handled since she was inappropriately shocked simply for being pregnant.

There is a question about who we want to be the gatekeepers for our software. She wants to have a say in that. For example, she would like to be able to gather pregnant women who have a defibrillator and put them together with a medical professional to study and perhaps modify the algorithm in the device. She wants that option; with proprietary software, she doesn't have it.

Rules

There is a balancing act, though. With free and open-source software, we have constructed a vibrant ecosystem where there is give and take with the commercial actors in that space. We can't succeed in our goals without corporate involvement. The early licensing regimes that we established, though, set clear boundaries between community and companies. It allowed us to set rules for the ways that companies could participate but still give the community some control.

There are many different licensing regimes and they work in different situations; there is no "one licensing approach fits all". But with copyleft, we set the rules in a particular way. If we do not get the complete source and the installation scripts, what can we do when things go wrong?

[PULL QUOTE: This idea of setting ground rules for company involvement is something that we have lost sight of. END QUOTE]

This idea of setting ground rules for company involvement is something that we have lost sight of, she said. We got so excited when companies got involved with free software; we got jobs (three-quarters of the audience has a job where free software is a critical part of it). But we have more ability to set the rules than we think we do. For example, developers can ask prospective employers to hold their own copyrights in their contributions to free-software projects; it may not be something to hold out for, but even just asking will help companies get the message that talented technologists care about it.

It is important to remember that short-term corporate interests are not always aligned with long-term community interests, or those of society. As technologists, we have special knowledge that companies need to build their products. That gives us leverage to talk to management about the long term. Most people want to be a good person, she said, so if you explain it in those terms, a lot of managers and lawyers will do the right thing.

With companies, or anyone really, if you give an inch, they will take a mile, Sandler said. When we give more control to companies in our communities, they take it. It is "very hard to walk it back", so if you are starting a new project or initiative, and are looking at the governance structure, offer a little bit less. Companies will work within established structures but it is hard to take back power that has been ceded.

Beeping

Recently Sandler started beeping at 1:10pm every day. It was the battery in her defibrillator, which was supposed to last a lot longer but had run down due to the shocks it administered. That meant it needed to be replaced.

She went to her doctor with a bunch of demands: a data dump from the old device, the device itself for her to play with, and for the new device to have its wireless communications disabled. Her old device did not have wireless, but her doctor said that was not possible with the new devices.

Suddenly she was worried that she would have to change her career. She has gotten threats because of her work with the Outreachy diversity program, so the idea that the device attached to her heart would be broadcasting wirelessly with no security "was just too much". She started to cry in the doctor's office and tried to explain the risk from a wireless-enabled defibrillator; it would mean that she had to change her entire life, she said.

The doctor agreed that it should be possible to disable the wireless piece of the device and suggested that they call each of the manufacturers. She spent lots of time with the nurse-practitioner calling them; most said "no", one said "yes" and then "no", and one would not talk on the speaker phone so they required the nurse-practitioner to relay all of the information. One manufacturer, BIOTRONIK, said that it did not have the ability to disable the wireless, but that she should not worry since its devices were "hack proof" because they had never been shown to be vulnerable. She suggested the company donate a few devices to be tested, but "they said 'no'".

Just as she was getting ready to leave the office, the doctor remembered a European company. That company turns out to have one device where wireless can be disabled. Communication with that device is done through magnetic coupling, which requires touch-distance. So she initially went in with "guns blazing" to get the source code for her device, but ended up simply asking that she did not broadcast to the world.

Sandler started to run a bit short of time for her talk (at least partly due to a few technical glitches along the way) so she picked up her pace a bit. She reiterated that LCA has been an important part of her story, her career, and her ability to advocate for software freedom. It is difficult to do that advocacy; either people do not understand software freedom or they are looking for an angle to monetize it. The idea that it is worth spending your time on the non-profit side is something that people are skeptical of, Sandler said. We cannot completely avoid proprietary software, but we can make our choices thoughtfully and try to find free alternatives. If we can consume more free software, it will mean that we are more likely to have alternatives to proprietary software that the non-technologists among us will be able to use.

LCA is a "magical conference" that helps her remember that there are people out there who care. In Hobart, Tasmania at LCA 2017, she and her SFC colleague Bradley Kuhn agreed that when they got low during the year, they would just say "LCA 2017" to each other to remember the conference and pick up their spirits. It is important to have a place where the important issues can be discussed, even if they are not agreed upon, and in venues that are not completely dominated by corporate interests. Unlike most conferences these days, LCA is that kind of place.

Returning to the theme, "hey, did you ever get ...", she said that she has more hope these days. She is dealing with a small European company that is trying to make inroads into the US market, so she has some leverage. She is a bit famous with some people regarding this topic, she knows medical device researchers, and she has more information than she ever did before. People often ask what she would do if she could go back in time and, besides getting Bitcoin, she would tell herself that she could actually make some change in this area. "This is the future we are building for ourselves", she said, our "future cyborg selves". Free and open-source software gives us an ability to make it a future that we want to have.

A YouTube video of the keynote is available.

[I would like to thank LWN's travel sponsor, the Linux Foundation, for travel assistance to Sydney for LCA.]

Comments (9 posted)

Open-source drug discovery

An apparent linux.conf.au tradition is to dedicate a keynote slot to somebody who is applying open-source principles to make the world better in an area other than software development. LCA 2018 was no exception; professor Matthew Todd took the stage to present his work on open-source drug discovery. The market for pharmaceuticals has failed in a number of ways to come up with necessary drugs at reasonable prices; perhaps some of those failures can be addressed through a community effort.

Todd started by noting that he must normally begin his talks by selling open source to a room that is hostile to the idea; that tends not to be a problem at LCA. The chemistry community, he said, is playing catch-up, trying to mimic some of the things that the open-source community has done. The first step was to apply these principles to basic research before moving on to drug discovery; the latter proved to be harder, since it's typically a process that is shrouded in secrecy.

There are hazards around using terms like "open source" when it comes to chemistry. Todd mentioned a 2013 article in the Guardian discussing his work; the first comment came from a certain "rmstallman" asserting that "open source" does not apply in this setting. An inconclusive argument followed. Todd still wonders whether he should be using "open source", but alternatives like "free drugs" have their own pitfalls, he noted.

The first project started in 2005, working on a drug called Pranziquantel. It is given to some 100 million people each year to deal with a particularly nasty freshwater parasite infestation. The molecule comes in two forms (enantiomers), one of which is effective while the other only serves to leave a nasty metallic taste in the mouth. That taste is evidently so bad that many people given the drug refuse to take it; there is thus a solid reason to want to create just the effective form of the molecule, but that was an expensive thing to do. Todd's group took on this problem, and decided to ask the world for help — something that is rarely done in the chemistry field.

Thus started a community called "Synaptic Leap", which was useful for a while but has now gone dormant. The group asked for ideas, but didn't get much until it brought in some grant money and started an online lab notebook. That was the crucial component; it reveals what is happening in the lab every day, shows that the group is actually leading the effort rather than just asking others to do free work, and makes the world take the effort seriously. Synaptic Leap was featured on a prominent chemistry blog, with mixed reactions overall, but a lot of people started to contribute. A company called Syncom did a lot of lab work and accelerated the work considerably.

A post to a LinkedIn room containing 1,000 process chemists brought in more help; as a side benefit, Todd said, it also found an actual reason for LinkedIn to exist. In the end, they solved the problem quickly, making good use of input from outside. The solution is working its way toward the market now.

The scientific community tends to talk a lot about "open innovation", but that has nothing to do with open source. In the former, a company with a problem will post it publicly, then buy a solution if somebody presents it. That solution will remain proprietary; "that doesn't really change anything". In the open-source world, instead, the solution, too, is out in the open.

Drug discovery

The next step is to try to discover new molecules that can be used to attack diseases. The usual process starts with some molecule that is effective against a disease (it kills the malaria parasite, for example), but which cannot be used because it is toxic to humans or has some other problem. By researching variations of that molecule, one hopes to move from a "hit" to a "lead" that is potentially usable as a medication. This process tends to happen in secret, but Todd and colleagues hoped to find a way to do it in the open instead.

It turns out that GlaxoSmithKline had published a paper identifying thousands of molecules that killed the malaria parasite; this information had been put into the public domain for anybody to work from. From this starting point began the Open Source Malaria (OSM) project. This project is based on six "laws" of open science:

• All data is open and all ideas are shared
• Anybody can participate at any level of the project
• There are no patents
• Suggestions are the best form of criticism
• Public discussion is more valuable than private email
• The project is bigger than, and not owned by, any given lab

The first three, he said, are the most important.

Open access is seen as increasingly important in the biochemical sciences. The Bill and Melinda Gates Foundation and the Wellcome Trust have been particularly aggressive in pushing open research, where the results and the data must both be available. The Open Source Malaria project agrees with all of that, but goes another step by making the laboratory notebooks available as well.

OSM has run four campaigns to date. Each campaign is essentially looking at a molecule until something useful is found or it becomes clear that nothing is forthcoming. Importantly, when the project gives up and moves on, it doesn't hide any of its data on the failing molecule; anybody can resume that effort in the future if they want. The first three campaigns at OSM have stalled out; the fourth is ongoing.

The bedrock of OSM is the open lab notebook. This is a bit challenging in this field, Todd said, because most of his colleagues still use a paper and pen. So the first step is to make everything electronic so that it can be shared. The project initially used LabTrove for this work, but development has been slow on that project. OSM has now transitioned over to LabArchives (seemingly not an open-source project) owned by the University of Sydney.

Then, the project needed a to-do list. There were a number of "extremely unfortunate" experiments with systems that didn't work out at all, until somebody came up with the idea of using GitHub's issue lists. The project has no idea what it's doing with GitHub, Todd said, but issue lists have been "sensational"; they have brought people in who are actually using them. The data for the molecules themselves is stored in a Google Docs spreadsheet.

The molecule that OSM is working on now is "very promising"; the work is at the point where somebody would normally be filing for patents. It works in mice, and it is getting close to being ready to try in humans. But the investigators still don't know how the molecule actually works, which "will eventually matter". They decided to run a competition to figure that out, and got six models submitted in return which they then tried against a separate, secret dataset. There were some winners in the competition, but none of the models worked particularly well; it seems necessary to retry the experiment with more data. The submitters all want to keep trying with more data, and they want to work together to figure out how to model what this molecule is doing. Todd believes that a predictive model will eventually result from this work.

Contributions to OSM don't just come from individuals, though; there has also been some good input from big pharmaceutical companies. The companies themselves cannot participate in something like OSM, but they can allow their people to do so. A scientist from Pfizer found and contributed an especially potent molecule; interestingly, when the OSM scientists synthesized it, it didn't work at all. So something is different somewhere; there is an open issue on GitHub dedicated to figuring that out. It is, Todd noted, especially important to be open about things that do not go right.

Work is happening in university classrooms as well. Some students have come up with molecules and have shown them to be effective, which is exciting for everybody involved. There was also an interesting episode where OSM worked with students to cheaply synthesize Daraprim; that is the drug that "pharma bro" Martin Shkreli increased the price of by a factor of 50. Working in a university lab, the students were able to create $150,000 worth of "primo-quality" Daraprim cheaply.

To summarize: OSM is a platform and a growing body of machine-readable knowledge. But it's also a community demonstrating ideas about how things can be done differently in the area of drug discovery. There have been issues about how discoveries from OSM can be published in the academic literature. Five years ago, that was a problem, but the journals have become much more receptive to publishing the results of open research. The openness of projects like OSM engenders trust in the results they get. Beyond that, people like to see how results are achieved. Just like people will watch the cooks in a restaurant with an open kitchen, they will watch how this kind of science is performed when it's open. That, in turn, helps people to quickly learn how the scientific community works.

Next steps

The next step would be to get one of these molecules into a clinical trial with humans; that would be the first time such a thing has ever happened with an openly developed molecule. There are just a couple of problems that need to be solved before that can happen. At that point, there will be new funding issues; human clinical trials have a number of ethical and legal issues that need to be worked out.

Dropping back into technical details, Todd noted that there still isn't any easy way to convert a molecule into a string representation. The form in which molecules are stored in the computer looks like:

    O=C(/C(S/1)=C/C2=C(C)N(C(C)=C2)C3=CC=C(S(=O)(N)=O)C=C3)NC1=N\C4=CC=CC=C4

Needless to say, such things are rather painful to type. The real problem is that, at present, computers don't understand molecules; if they did, lab notebooks would be far more useful. It would be possible to search for people working on similar molecules, for example. There is a proposal out there for a system called SCINDR to introduce scientists to possible collaborators; building that requires better machine-readable lab notebooks. Projects like C6H6 are a step in the right direction, but there is work to be done in this area still.

There are various other details that need to be solved. A better web page would be a good start ("we don't know what we're doing there"). A tool to automatically move data between the Google document and public databases is on the list. With a reference to the discussion at the previous day's opening session (which was a celebration of LWN's 20th birthday) he noted that newsletters are important, and the project is about to put out its first issue. There are thoughts of becoming a non-profit organization. The project has T-shirts, but he observed at the conference that stickers are needed too.

The biggest thing that's missing, though, is automatic construction of narratives. When somebody is doing work, one of the most important things to do is to reflect that work in a wiki, but that rarely happens; people are too busy. It would be nice to have this happen easily, with a simple "publish" button to hit at the end. There is scope for research into AI systems that could help with this task.

There is a new project, the Drugs for Neglected Diseases Initiative (DNDi), which seeks to expand this approach to diseases that tend not to attract attention from pharmaceutical companies. The first topic is a nasty fungus called Mycetoma that, currently, has no treatment other than amputation. The DNDi is launching its first clinical trial for a new molecule in this area, and others are in the works. This is a good target: the need is immediate and there is nothing available for this disease now.

A question he is often asked is: who is going to pay for this kind of work? How can a drug be brought to market with no secrecy? There are a number of different initiatives in this area, many of which are discussed in this 2017 paper co-authored by Todd. There is a lot of money from foundations going into drug discovery. The real problem is a lack of precedent for an openly discovered molecule going into production; that hampers funding of the crucial clinical-trial phase. What is needed is the sort of corporate investment that is seen in the open-source industry; there's currently nothing like it in the pharmaceutical business. In the field of law, companies require that their legal staff do pro-bono work; that, too, doesn't happen in pharmaceuticals. He hopes that will change in the next few years.

Some people feel that drug development cannot be done without patents, but that is clearly not the case, he asserted. Penicillin and polio medicines were never patented. One of the most widely used antimalarial drugs (ASAQ/Coarsucam) is patent-free, as is Fexinidazole, a new drug for sleeping sickness. He thinks there is a workable model that enables investment from companies that allows them to get their money back when they need to. Under this "data exclusivity" model, any company that pays for the trials that show a molecule to be effective and safe would get exclusive rights to sell it for six years. That clock would only start when the drug hits the market, a feature that can make this approach more attractive than patents, for which the clock can start many years before the drug can be sold. After six years, the drug would go generic.

The one thing that worries him, he concluded, is that there is continual talk about how new approaches are needed in this field, but they are not happening. Alzheimer's and dementia are a looming catastrophe, for example, but we have no answers for these problems. The current approach isn't working to solve them, but nobody is doing anything differently. If we generally want to try radical approaches, we need to try the things that the pharmaceutical industry cannot do, and that requires working collaboratively in the open.

Interested viewers can watch the full video of this talk.

[Your editor thanks the Linux Foundation and linux.conf.au for assisting with his travel to the event.]

Comments (3 posted)

F-Droid: an alternative to Google Play

It is important to talk about Android at Linux conferences like linux.conf.au, Peter Serwylo said to start his talk. Android is deployed on millions or billions of devices, but it does suffer from some problems that F-Droid, an alternative Android app store, tries to address. The title of his talk noted that F-Droid is private, secure, free, and open, all of which are desirable traits for many in our community.

Serwylo got interested in Android because it was running on the first smart device he ever owned. He chose Android because he was getting interested in free software and recognized that Android was a well-supported version of Linux that was available on lots of different devices. But he found that the Android experience was not quite the "Linux experience that you are used to".

To start with, the first thing you have to do with a new Android phone is to sign into a Google account. Part of that is agreeing to the terms of service. There is a helpful "Skip" button, but if you use that, you cannot install any apps on the device. If Debian's installation had something similar, it would not be tolerated by most. But phone makers that want to distribute Android must do it "the Google way", which includes installing the Google Play Services that require the sign-in and agreement. That is the "Google Android experience", which he is not particularly interested in, he said.

So instead of Android the product, he wanted to focus on Android the technology as embodied in the Android Open Source Project (AOSP). It is the free system that he was hoping for, he said. AOSP is a Linux kernel and a bunch of user-space pieces that app developers use. As an app developer who cares about freedom, he is interested in the Android Framework that is released as part of AOSP. If an app developer wants their program to work on as many devices as possible, they will use the Android Framework; this allows alternative operating systems to still be able to run the apps that are available for Android.

For those who do not like the Google experience for one reason or another, there are some different "ROMs" available to install. These ROMs typically come with scary instructions on how to install them, however. It used to be that you would go to the XDA Developers Forum and get pointed off at some site where you could download the software to run on a device that you carry everywhere; there are now some established ROM projects. Three of the most prominent ROMs are LineageOS (formerly CyanogenMod), which is focused on supporting many devices, Replicant, which has a focus on freedom, and CopperheadOS, which has a security focus. These are well-run projects that provide an experience that is much more like a regular Linux distribution.

But even if you run one of the alternative ROMs, you will want to get software on your phone, he said. One of the common questions for users of those distributions is "how do I install the Play store?" The answer is to download the app (and supporting libraries) from a dodgy site, which is all rather scary. In addition, doing so means you have no license to actually run the code.

Enter F-Droid

This is where F-Droid comes in, Serwylo said. F-Droid provides an alternative to Google Play. There are actually lots of app stores in the Android world; this is different from the Apple world that is largely locked into a single app store. The most famous alternative Android app store is probably Amazon's, which sells the Amazon experience rather than the Google experience. There are many others, however, that typically spring up out of necessity. For example, China blocks access to the Play store, so there are multiple alternative stores. Another is APTDroid, which is what F-Droid was forked from after APTDroid moved away from a focus on freedom. There are many of them out there, some with a regional focus (e.g. Iran), and F-Droid is just another, but it is one that he thinks is much better than the others.

The F-Droid app has the features one would expect from an app store. You can search and browse for apps, get notified of updates, and so on. There are app categories for browsing and all of the searching is done offline, "which is nice", he said. You can look at the details of an app, including screen shots; unlike other app stores, F-Droid publishes older versions of the apps too.

There are other things that F-Droid does that other app stores don't. For example, you can turn your phone into a mini app store; others can download apps from your phone using Bluetooth or wifi. That feature is particularly nice in places where the internet is not easily (or reliably) available. You can still keep the Play app installed if you have the F-Droid app; in addition, the F-Droid app can access multiple repositories beyond just the official one. All of the apps on the official repository are free software, but Serwylo recommends that new users keep the Play store; "otherwise you might be horrified at the amount of stuff you are missing out on".

F-Droid is really a package manager for Android. Packages are built from source and signed by F-Droid, but no account is needed to download these packages. So there is no user tracking; in addition, there is no advertising in the store. It works like package managers for regular Linux distributions. Decentralization is also part of the puzzle since multiple repositories are supported; anyone can spin up their own, much like personal package archives (PPAs) for Ubuntu.

There is a "big stack of software" that makes up F-Droid, starting with the fdroidclient, which is the app that the user sees. Some who have rooted their phones can install the privileged-extension, which gives F-Droid the same level of access as the Play app. The fdroidserver is a bunch of command-line tools for curating an F-Droid repository: building and signing packages, producing metadata, and uploading packages. Build metadata for over 2000 open-source apps is stored in the fdroiddata repository, while new apps can be added by using the rfp (request for packaging) repository. There are some other parts and pieces, but those are the most important, he said.

Part of the reason that the F-Droid project cares so much about "privacy, security, and freedom" is that many of its users are vulnerable. They are activists and civil libertarians in places where the government does not want that, for example. That means it is important for those users to protect themselves and their personal devices.

Getting an app onto F-Droid

Serwylo then stepped through the process of getting an app onto F-Droid while highlighting some of the privacy, security, and freedom considerations at each step. It was meant to be a "whirlwind tour of how we take care of the user".

The first step is sourcing the app, perhaps from a GitHub repository. In order to be added, the app must be free and open-source software and must not depend on Google's Play Services. The app developer would submit a request for packaging, which will (eventually) get picked up by one of the two or three active maintainers (more help needed here, he said). The maintainers will create the build metadata after ensuring that the app does not depend on non-free software; they will also flag any anti-features that they find, though some may slip through. For example, if the upstream of the app is non-free, such as for a GitHub client, that will be noted for the package metadata.

The next step is to build the app. Building thousands of apps "could be considered a dangerous pastime from a security perspective", as the F-Droid documentation notes. This is handled by building each app inside its own virtual machine, which is connected to the internet so that dependencies can be fetched. Unfortunately, the Java Maven repository provides no real way to check the signatures on its packages, which is a bit of a hole at this point, he said.

Something that could be done to thwart a man-in-the-middle attack against the F-Droid build machine would be to have verification servers that also build the package. If reproducible build techniques are used, the hashes of those packages can be compared. There is a verification server running, but that information is not used by the client at this point. It would be great ("contributions welcome") if the client could check with three separate servers. Serwylo did not mention it specifically, but given the difficulty of checking Maven signatures, having packages replaced with malicious versions would still seem to be a problem.

Next up is signing packages. Android has "quite a nice signing model", he said; it will only install signed packages and will only update a package that is signed by the same key as the original package was. There are several different levels of signing, from a developer signing on their laptop that is on the open wifi at some local restaurant (not recommended, of course) to using an air-gapped machine and hardware security module for signing. The latter is what F-Droid uses.

But there is still a problem. If a user has installed an app from the Play store, which is signed by the developer's key, it cannot be upgraded via F-Droid, because the keys differ. Users would need to uninstall and reinstall the app, which is painful, especially for apps with a lot of configuration (an email client, say). The solution is similar to the verification server idea, though it is more complicated. By using reproducible builds, F-Droid can verify that a package signed by the developer's key is the same as what was built from source. It can then distribute both the developer-signed package and the F-Droid-signed package. The problem is that, unlike the verification server, F-Droid does not directly control the build environment for all of the app developers, so build reproducibility will be impacted.

Once the package is signed, there needs to be a way to get the metadata across the internet to the client that may be in a hostile environment. The client will only trust metadata that is signed with the F-Droid key (or the key for another repository that the user has chosen to add). That metadata contains the hashes of the binaries, as well as the usual description, version number, and the like, so it is important to ensure it is not tampered with.

A feature that has not been added yet, but should be coming soon, is to add per-ROM certificates so that one of the ROMs can ship F-Droid with the ROMs certificates pre-installed. That will allow users to get apps and updates directly from the distribution. Any certificates that are not installed with the F-Droid app can be accepted on a "trust on first use" basis.

F-Droid respects privacy by not requiring accounts and by sending everything over HTTPS. In addition, it has first-class support for Tor and other proxies. Another thing the project cares about is not leaking information about browsing and searching for packages, which is why they are done locally. Beyond that, the metadata contains all of the supported languages as well, so that the server does not get any information about the user's language setting.

There is support for repository mirrors, though the official F-Droid repository does not have any at present. However the Guardian Project has a half dozen for its repository. Those mirrors are on lots of popular domains (e.g. amazonaws.com, githubusercontent.com, gitlab.com), which makes it harder for a repressive regime to cut off access. The Guardian Project calls this "collateral freedom", Serwylo said.

Installing a new app is done by downloading it from the server and then checking the hash in comparison to the value in the metadata. That way F-Droid can detect if the package has been tampered with. When it is doing that check, however, it needs to ensure that it does not use Android's external storage. Otherwise, any app with the proper access could replace the package after the hash check but before F-Droid has requested that it be installed.

Google Play is able to install apps via "magic", he said; it is a blessed app with special privileges that few other apps have. This is where the privileged-extension comes into play. By installing that, you can give F-Droid the same level of blessing so that it can install apps. Otherwise users must enable installation from unknown sources ("a euphemism for 'not Google Play'", he said). The problem is that enabling that means that other apps can also request package installation, "which is a little scary". Later versions of Android allow giving that permission to individual apps, which makes things a bit less scary.

The project has put a lot of thought into freedom, security, and privacy, he said. Little of what has been done is truly new, in some ways it is rebuilding infrastructure that already exists, but the project started small and grew organically over time. He hopes that F-Droid will help people start thinking about their phone as their own device, where they can securely install their choices, rather than a kind of disposable device that they get from Google and other providers and move on from in a year or two.

A video of the talk in multiple formats is available from archive.org.

[I would like to thank LWN's travel sponsor, the Linux Foundation, for travel assistance to Sydney for LCA.]

Comments (9 posted)

4.16 Merge window part 1

As of this writing, just over 6,700 non-merge changesets have been pulled into the mainline repository for the 4.16 development cycle. Given that there are a number of significant trees yet to be pulled, the early indications are that 4.16 will be yet another busy development cycle. What follows is a summary of the significant changes merged in the first half of this merge window.

Core kernel

• Initial support for the Jailhouse hypervisor has been added for the x86-64 architecture. With this support, it's possible to run Linux in a non-root cell.
• The deadline scheduler has been given an understanding of CPU frequency and voltage scaling; that allows it to operate properly without the need to disable power-saving features.
• The arm64 architecture can now work with 52-bit physical addresses on suitably equipped hardware.
• The Berkeley Packet Filter (BPF) virtual machine now has support for the defining and calling of functions within BPF programs.

Filesystems and block layer

• The MultiMediaCard subsystem (which handles storage devices like Secure Digital cards) has been reworked to use the multiqueue block API. That should bring performance improvements among other benefits.

• The I/O schedulers have gained support for locked zones on block devices; this is used to prevent reordering of writes on zoned devices where writes must be performed sequentially.

• The CIFS filesystem has experimental support for SMB Direct, which can use remote DMA (RDMA) to transfer SMB packets.

• The Btrfs filesystem now supports the fallocate() FALLOCATE_FL_ZERO_RANGE operation.

• The NFS client can now use the query flags in the statx() system call to avoid calling to the remote server if the needed information is available locally.

• The new RWF_APPEND flag to pwritev2() will append the data to the file regardless of the current offset.

Networking

• The new "netdevsim" virtual device exists to help in the testing of hardware-offload features in the networking stack. It simulates various offload operations so that higher-level code can be tested without the relevant hardware being present. The initial use case is for testing BPF offload support.

• The Netware IPX and NCPFS protocol implementations are old, unmaintained, and unused; they have been moved to the staging tree ahead of their eventual deletion from the kernel.

Security-related

• The arm64 architecture has gained the ability to invalidate the branch prediction unit, a defense against the Spectre variant-2 vulnerability. Also added to arm64 is kernel page-table isolation to defend against Meltdown.

Hardware support

• Audio: Texas Instruments PCM186x and TLV320AIC32x4 codecs, Texas Instruments TAS6424 quad-channel audio amplifiers, Maxim integrated MAX98373 speaker amplifiers, STMicroelectronics STM32 DFSDM digital audio interfaces, Tempo Semiconductor TSCS42xx codecs, and Socionext UniPhier LD11/20 codecs.
• Bus: Eckelmann SIOX buses, SLIMbus buses, Qualcomm SLIMbus controllers, and SoundWire two-pin buses.
• Cryptographic: STMicroelectronics STM32 CRYP1 cryptographic accelerators, Chelsio IPSec XFRM Tx crypto offload engines, and Samsung Exynos true random number generators.
• Industrial I/O: IDT ZOPT2201 ALS and UV B sensors and STMicroelectronics UVIS25 UV sensors.
• Networking: Hisilicon HNS3VF network acceleration engines, MediaTek MT76x2E wireless network interfaces, Socionext AVE Ethernet interfaces, SocioNext NetSec gigabit Ethernet controllers, and Cortina Gemini Ethernet controllers.
• Miscellaneous: Realtek rts5260 card readers, RAVE supervisory processor units, Nuvoton W83773G hardware-monitoring chips, Spreadtrum SC2731 power regulators, Texas Instruments DDR3 ECC controllers, Texas Instruments LM3692x LED controllers, Winbond Super I/O GPIO controllers, and Oracle SPARC data analytics accelerators.
• The LED subsystem has a new trigger type (NETDEV) that can trigger an LED based on network activity.

Internal kernel changes

• The handling of the inode i_version field has changed to eliminate changes (which must be expensively flushed to storage) when nobody is paying attention. There is a new API (found in this commit) for working with i_version.
• High-resolution timer (hrtimer) functions have traditionally run in hard-interrupt context. Many users actually need to be running in software-interrupt context, though, leading to a situation where a lot of hrtimer functions do nothing except start a tasklet to get the real work done. 4.16 adds two new timer modes (HRTIMER_MODE_REL_SOFT and HRTIMER_MODE_ABS_SOFT) that run the timer function in software-interrupt context to begin with, eliminating the need for the tasklet.
• The return type of the poll() method in struct file_operations has been changed to the new __poll_t type. It is a bitwise type that facilitates automatic checking for a number of common mistakes in poll() implementations.
• The new snap-pkg target in the build system can be used to create a Snap package containing a built kernel.
• The parser used by the configuration system is now directly generated with flex and bison; those tools are thus now part of the kernel's build requirements.

The 4.16 merge window will probably close on February 11; the final 4.16 kernel release can, barring another significant security surprise, be expected on April 1 or 8. Stay tuned for the second article in this series, which will cover the second half of the merge window for this development cycle.

Comments (14 posted)

Meltdown and Spectre mitigations — a February update

The initial panic over the Meltdown and Spectre processor vulnerabilities has faded, and work on mitigations in the kernel has slowed since our mid-January report. That work has not stopped, though. Fully equipping the kernel to protect systems from these vulnerabilities is a task that may well require years. Read on for an update on the current status of that work.

Variant 1

Perhaps the biggest piece of unfinished business in January was a proper response to Spectre variant 1 — the bounds-check bypass vulnerability. Variant 1 is likely to be difficult to fix at the hardware level, and so may be with us for a long time. Unfortunately, it is also difficult to address at the software level.

The seemingly final form of the patches for variant 1 has changed the interface yet again. Consider a simple code fragment that might be vulnerable to speculation that bypasses a bounds check:

    if (index < ARRAY_SIZE)
	return array[index];

The way to protect this kind of reference to ensure that no out-of-bounds references to array occur would be:

    if (index >= ARRAY_SIZE)
    	return 0;  /* Or whatever error value makes sense */
    else {
    	index = array_index_nospec(index, ARRAY_SIZE);
	return array[index];
    }

The protective macro array_index_nospec() no longer actually accesses the array; instead, it just manipulates the index value in a way that blocks speculation. It uses the masking technique described in the mid-January article, avoiding the rather more expensive barrier operations entirely. For cases where the operation that needs to be protected is more complex than a simple array access, there is another macro called barrier_nospec() that does use a barrier to block all speculative activity. It is rather more expensive to use than array_index_nospec(), on the x86 architecture at least, but sometimes there is no alternative.

Actual uses of these new macros are relatively scarce at the moment. The get_user() function in the kernel is one area of concern, since it can be used to attempt an access to an arbitrary address in the kernel; since get_user() has the necessary bounds check to ensure that the given address points into user space, adding a call to array_index_nospec() (more correctly, an optimized assembly version of it for x86) is enough to prevent problems. The __get_user() variant, though, lacks those checks and is invoked in well over 1,000 call sites in the kernel. Protecting __get_user() requires tossing in a barrier_nospec() invocation.

Another area of concern is the system-call table, which is indexed using an integer value (the system-call number) from user space. A call to array_index_nospec() is used to prevent out-of-bounds access to that table. Protections have also been added for file-descriptor lookup, in the KVM code, and in the low-level wireless networking code. Nobody believes that all of the potentially exploitable places have been found, though.

Meanwhile, there is an arm64 patch set in circulation with mitigations similar to the x86 patches. It has fewer mitigations currently It doesn't repeat the non-architecture-specific mitigations found in the x86 tree, but does add protections to the futex() system call that are not currently present (and maybe not needed) for x86.

Finding the remaining locations where variant-1 protection is needed is likely to require fairly advanced static-analysis tools. The work done so far has relied on the proprietary Coverity tool, and has had to contend with a high false-positive rate. Everybody involved would like to see a free tool that could do this work, but nobody is apparently working on such a thing. That is certain to slow the rate at which vulnerable code is found and increase the rate at which new vulnerabilities are introduced.

Arjan van de Ven has suggested that what really needs to happen is a centralization of many of the security checks that are currently dispersed throughout the kernel. He recommends the creation of a utility function described as:

    copy_from_user_struct(*dst, *src, type, validation_function);

Where the validation_function() would be automatically generated from the UAPI headers that describe the interface to the kernel. Widespread use of a function like this would free most developers from the need to worry about Spectre variant-1 vulnerabilities; it might also improve the (not always great) state of argument validation in general.

Variant 2

Spectre variant 2 (branch prediction buffer poisoning) has been mostly mitigated by way of the "retpoline" mechanism that was merged for the 4.15 kernel release. With the GCC 7.3 release, a retpoline-capable compiler is finally available. There are, however, a number of loose ends that are slowly being dealt with.

There is still a fair amount of uncertainty around the question of when retpolines provide sufficient protection. The "indirect branch prediction barrier" (IBPB) operation provided by Intel in recent microcode updates will protect against poisoning, but its use is expensive, so there is a desire to avoid it whenever possible. There are cases, though, such as switching into and out of a virtualized guest, where IBPB is needed.

There is also the inconvenient fact that Intel released a number of microcode versions with implementations of IBPB that, to put it politely, did not function as well as users would have liked. Dealing with that last problem requires avoiding IBPB entirely on the affected microcode versions. There was some discussion over whether the kernel should blacklist known-bad versions or use a whitelist of known-good alternatives; the latter approach was somewhat driven by worries that Intel was never going to get things right. In the end, though, the blacklist approach won out, on the theory that the problems have, in the end, been fixed.

Similar concerns relate to the "indirect branch restricted speculation" (IBRS) barrier-like operation that, by some accounts, is needed to get full protection on Intel Skylake-generation processors. That, too, has had issues with some microcode versions. Those too, with luck, have been fixed; if not, David Woodhouse warned: "then I think Mr Shouty is going to come for another visit."

There is still some resistance to using IBRS at all, though. It also is an expensive operation, and nobody has demonstrated an exploit on Skylake processors when it is not used. Meanwhile, Ingo Molnar has proposed a different approach: use the ftrace machinery to keep track of the number of entries in the return-stack buffer (RSB) and force the use of a retpoline when it gets too deep. It is not yet clear that this idea can be implemented in a practical way; Thomas Gleixner has played with it but he ran into some complications and set it aside for now.

One concern about variant 2 is that it might lend itself to attacks by one user-space process (or thread) against another. JavaScript code running in a browser appears to be the most likely vector for such an attack, but it's not the only one. This patch, for example, is an attempt to protect high-value processes by issuing an IBPB barrier prior to switching into a process that has marked itself as being non-dumpable. The idea is to provide some protection for programs like GnuPG while avoiding the overhead of IBPB on every context switch.

Other odds and ends

Protection against Meltdown ("variant 3") was mostly in place when the embargo fell in January; its basic form has not changed much since then. There are numerous bugs to fix, of course, and that work has been ongoing. The arm64 architecture gained kernel page-table isolation during the 4.16 merge window. There has also been some work on the x86 side to avoid using kernel page-table isolation on systems that do not need it — AMD processors and ancient Intel processors, for example. The whitelist of safe processors is slowly growing.

Systems with Meltdown and Spectre mitigations also have a new sysfs directory (/sys/devices/system/cpu/vulnerabilities) listing known CPU vulnerabilities and their mitigation status. On your editor's laptop, they currently read:

    meltdown:	Mitigation: PTI
    spectre_v1:	Vulnerable
    spectre_v2:	Mitigation: Full generic retpoline

There have been some concerns that these files, which are world-readable, provide useful information to attackers and should be restricted. On the other hand, Alan Cox responded, that this information is already readily available and it can be useful to utilities like just-in-time compilers, which might change their output when certain vulnerabilities are present. As of this writing, no patches changing the protections on those files have been merged.

Other than that, though, everything described here has been merged for 4.16 and is quickly headed toward the stable kernel updates as well. There are a number of smaller issues not described here that were also addressed for 4.16; see this pull request for the full list. Clearly, even if things have slowed a bit to allow the developers involved to get some sleep, a lot is still happening to deal with the fallout from Meltdown and Spectre.

Comments (17 posted)

Mixed-criticality support in seL4

Linux tries to be useful for a wide variety of use cases, but there are some situations where it may not be appropriate; safety-critical deployments with tight timing constraints would be near the top of the list for many people. On the other hand, systems that can run safety-critical code in a provably correct manner tend to be restricted in functionality and often have to be dedicated to a single task. In a linux.conf.au 2018 talk, Gernot Heiser presented work that is being done with the seL4 microkernel system to safely support complex systems in a provably safe manner.

The world contains an increasing number of "cyberphysical systems" implementing various types of safety-critical functionality. Fly-by-wire systems for aircraft and factory automation systems are a couple of examples. These systems are subject to an expensive safety-assurance process with costs that scale linearly (at least) with each line of code. When one considers that an Airbus A380 jetliner contains around 120 million lines of code, one can understand that developing that code can be a costly business.

The traditional approach to safety-critical code has been physical separation, using a different microcontroller for each function. That is how cars and aircraft have been built for some time. But those controllers are not cheap; a microcontroller fit for deployment in an automobile must be waterproof, resistant to dust, grease, acids, and vibration, and be able to operate in a wide range of temperatures. Such controllers are expensive, and there were typically about 100 of them in a car even five years ago. They are heavy, require a lot of cabling, and use a lot of energy.

The problem is compounded by the increasing need for sensors. Many sensors in a car support a number of different functions, meaning that they must be shared across processors.

The answer to this problem is consolidation: get a bigger processor and put a number of functions on it. That reduces costs while allowing better integration between functionalities; that integration is absolutely needed for autonomous vehicles. But this approach loses the physical isolation between functions, so that isolation must be restored in some other way that can still achieve certification.

Getting there, Heiser said, "involves killing a lot of trees". Specifications and development documents must be written. Effort must be put in to attach every requirement in the specifications to the lines of code that implement it. This work is expensive, to the point that, for the highest safety levels, the cost is prohibitive for anything more than a few thousand lines of code.

The answer is to use software isolation to separate the safety-critical code (which must be certified) from everything else. This an old concept, "in use since the stone age", but there is a problem: operating systems are hopeless at providing this kind of isolation. They do things like put device drivers into the kernel. Anything in the system can affect anything else. This kind of operating system cannot be used for systems of any complexity, he said.

Isolation starts by defining the "criticality" of every task that the system must perform. There are several levels, based on the consequences that result if the system fails to do its job properly; they go from "harmless" to "catastrophic". On any system running tasks with varying criticality, no task may depend on anything at a less critical level.

Solving the problem with seL4

The system that can support mixed-criticality workloads, Heiser said, is seL4. It completely isolates all running components by default, but makes it possible to create communication channels between components where they are needed. Its core mechanism is called "capabilities", but they differ from the capabilities found on a Linux system. A seL4 capability is an access token: it contains a reference to some object and a set of associated access rights. Processes must present the necessary capabilities with any operation, and the system will make a decision as to whether to allow that operation. It adds up to a fine-grained access-control mechanism.

There are eight different types of capability-protected objects in seL4:

• Thread-control blocks (processes)
• Address spaces
• Endpoints (ports for communications between processes)
• Notifications (a sort of completion mechanism)
• Capability spaces (to store capabilities themselves)
• Frames (areas of physical memory that can be mapped into address spaces)
• Interrupt objects
• Untyped (free) memory

All of these object types are "spatial", he said; the lack of any concept of time is a longstanding seL4 issue (which he was to return to shortly).

The seL4 microkernel has been subjected to a set of formal proofs of its security and safety properties. It is based on an abstract model written in a mathematical notation that is used to generate the C implementation. There is a machine-checked proof that the C implementation actually holds to the specification, and another proof that things are not broken in the compilation process. Yet another set of proofs show that the model implements the needed confidentiality, integrity, and availability properties. SeL4 is, he said, the only operating system in the world that has been verified in this way.

There has also been a worst-case execution time (WCET) analysis of all kernel operations that, he said, shows that seL4 is the world's fastest microkernel. Aspects that have not yet been verified are the initialization process, some memory-management unit operations, and multicore operation — but that work is in progress.

Toward a certifiable mixed-criticality scheduler

Once again, he noted that all of this verification only applies to spatial isolation, but the WCET work is a good start on the temporal problem. Beyond that, there is a new scheduling model in the works that will ensure that low-criticality code cannot interfere with higher-criticality code. The existing seL4 scheduler is relatively primitive, based on round-robin realtime scheduling that rotates through the runnable processes with the highest scheduler priority; it is good, but not sufficient. Among other problems, this scheduler will let the highest-priority process monopolize the CPU for as long as it chooses to. (Here, as usual, "priority" is a value used by the scheduler to pick the process to run first; it is not the same as the criticality assigned to any given functionality, though high-criticality tasks tend to be given high priorities).

As an example, consider a network driver. It will not be the most critical task on the system, but it may still need to occasionally preempt a high-criticality control loop to avoid losing packets. With the current scheduler, that driver must be given a high priority and trusted to not hog the CPU.

Another problem is data structures that are shared between criticalities. A common solution is to encapsulate that data in a separate server, running in its own address space. Other processes then communicate with the server to access the structure. Priority-inversion problems can result, though, when processes with different priorities access the server. Use of the priority-ceiling protocol can help, but requires getting the priorities set right. There are still problems where one client can starve another by repeatedly invoking the data-structure server, though.

Improving the situation naturally involves another set of requirements. A new scheduler must provide certifiable spatial and temporal isolation. It must be able to guarantee deadlines for high-criticality tasks while being able to share resources across criticalities. It should run low-criticality processes during otherwise slack periods. Capabilities should be used for time control.

Getting there, Heiser said, is not that hard with the right model. The classic time slice has been replaced by a "scheduler context". That, when combined with a capability, can be used to assign a given CPU budget and period to each process. Any process that exceeds its CPU budget during a given period can be throttled. Processes that have shorter periods are given a higher priority by the scheduler, but the budget limits the amount of CPU time that even the highest-priority process can consume.

The scheduler works by always running the highest-priority thread that has a non-zero budget. Any thread that has consumed its budget waits until the next period begins. If there are multiple processes with the same priority, round-robin scheduling is used.

In this model, the shared data-structure server mentioned above has no scheduler context of its own. Instead, it will use the context of the clients that invoke it. That causes this server to run at a priority appropriate for the client it is serving while charging that client for the CPU time used. It's a neat solution, but there is one little problem: what happens if the client's budget runs out while the server is running? These servers are usually single-threaded to keep them simple and certifiable, so simply throttling the server would deny service to other processes that may need it.

There are a few options for dealing with this situation. One would be to require that such servers be multithreaded; adding concurrency adds complexity, though, so this is not a great solution. Another would be to throttle the server until another client comes along, then borrow that client's time to finish the first client's work. In this case, the wrong process is paying for the mistake, which is not a good thing. The solution chosen for seL4, instead, is to provide a mechanism called "timeout exceptions". They can respond in a number of ways, including resetting the server, providing an emergency CPU-time budget, or implementing priority inheritance "if they really need to".

This new scheduler solves the problem, but it does not come for free: interrupt latency increases by 11% and scheduling itself is 19% more expensive. In both cases, the need to reprogram hardware timers is the source of most of the slowdown. But, he noted, scheduling in seL4 is "still an order of magnitude faster than Linux".

He wound down by noting that this work is being used in some real systems now. There are a couple of autonomous trucks under development for the US Army that are using it, and Boeing is working on a full-size autonomous helicopter. Certainly, as that helicopter flies overhead, one would hope that seL4 is indeed living up to its guarantees.

The video of this talk is available on YouTube.

[Your editor thanks the Linux Foundation and linux.conf.au for assisting with his travel to the event.]

Comments (39 posted)

Jupyter: notebooks for education and collaboration

The popular interpreted language Python shares a mode of interaction with many other languages, from Lisp to APL to Julia: the REPL (read-eval-print-loop) allows the user to experiment with and explore their code, while maintaining a workspace of global variables and functions. This is in contrast with languages such as Fortran and C, which must be compiled and run as complete programs (a mode of operation available to the REPL-enabled languages as well). But using a REPL is a solitary task; one can write a program to share based on their explorations, but the REPL session itself not easily shareable. So REPLs have gotten more sophisticated over time, evolving into shareable notebooks, such as what IPython, and its more recent descendant, Jupyter, have. Here we look at Jupyter: its history, notebooks, and how it enables better collaboration in languages well beyond its Python roots.

History

Python also has an enhanced REPL called IPython, which adds a host of abilities similar to what is available in an integrated development environment, such as a help system and tab completion. IPython offers some special features well-suited to Python's popularity as a language for scientific computation and analysis, such as smooth integration with matplotlib and other graphics packages and parallel computation. The architecture of IPython allowed it to be used as an interface for other interpreted languages besides Python, by writing a "kernel" to communicate between the host language and the interactive shell.

Early in its development, IPython gained an alternative interface called the "IPython Notebook." This was a web-browser based interface similar to the pioneering notebook interface used in the commercial symbolic mathematics program Mathematica. The IPython Notebook inherited IPython's ability to interact with other languages besides Python, and began to be used with R, Ruby, and others.

Beginning a few years ago, the notebook component of the IPython Notebook was split from the main IPython project to stand on its own. The new project is called Jupyter (the name is a loose acronym derived from "Julia", "Python", and "R", some of the first languages that the technology supported). The software, actively developed on GitHub with over 300 contributors, is organized under the umbrella Project Jupyter. The project is committed to remaining free and open-source; it uses the three-clause BSD license. Jupyter has a vibrant and enthusiastic user and developer community, with over 700 participants attending an annual conference. It survives through donations from users and the direct financial support of a handful of organizations and corporations.

Project Jupyter is organized around a "steering committee" of 15 members, including Fernando Pérez and Brian Granger, the original leaders of the IPython Notebook project, and a diverse group employed by a wide variety of academic and corporate institutions. Pérez and Granger describe its aims and philosophy, and some additional aspects of his history, in this overview of "The state of Jupyter".

The Jupyter interface offers several advantages over the traditional terminal-based REPLs. When you use Jupyter, your input and the program's output are automatically preserved on the page, forming a "notebook" that you can return to later and share with colleagues or students. You can interleave markdown-formatted, explanatory text between your interactions with the program, turning the notebook into something worthy of the name, or into the outline of a paper or textbook. Program output is not limited to text, but can include graphics, which can be embedded into the page. The pedagogical possibilities of the Jupyter notebook are expanded further by the ability to include widgets, such as sliders, for interacting with programs.

Those with experience with some past attempts at this kind of interface may suspect that Jupyter is clumsy and slow, but this is not at all the case. Interacting with Jupyter is a speedy, smooth, and responsive experience, which provides tab completion and syntax highlighting.

Jupyter kernels are usually written in the host language, but, for languages that can be controlled from Python, another option is to write the kernel in Python. Since the system uses a web browser, starting Jupyter also starts up a local web server to handle communication between the browser and the kernel.

Because of its origins, Jupyter is installed with the Python kernel and that is the only one required for its operation. The popularity of the Jupyter concept has led developers to continue to create kernels for a wide variety of languages besides Python, including C, Clojure, Julia, R, Fortran, and many others . Some of these (a partial list can be found here) are young projects and in early stages of development, while others are quite mature. One interesting thing to notice here is that Jupyter can be used not only for interpreted languages such as Python and Ruby, but for compiled languages such as C and Fortran, providing a vaguely REPL-like experience for developing in these languages. On a personal note, after I belatedly discovered that there is a gnuplot kernel available for Jupyter, it immediately became an indispensable part of my workflow for putting together a book about gnuplot.

The Jupyter project has become quite popular, especially with teachers and researchers using Python in data science, computational physics, and several other fields. Its reputation has grown as a convenient solution to the longstanding problems of sharing code and algorithms with co-researchers, or providing extra documentation on computational methods that was too detailed to be included in a published paper. A curated list of example Jupyter notebooks from its user community, indexed by topic and purpose, is available.

There are other programs, both free and non-free, that employ a notebook interface similar to IPython Notebook and Jupyter. Perhaps the most well-known commercial offering is Mathematica, which shares Jupyter's cell structure (see below) and embedded graphics; the free software statistical platform R has the R Notebook; the Python-based mathematical software package Sage featured its own notebook interface, but it has now been superseded by Jupyter; and there are several others. But Jupyter is unique in that it is designed to serve as a general notebook that can work with any programming language, or several at the same time — as long as the appropriate kernels are available.

Using Jupyter

It is possible to try Jupyter out without installing it; we'll explain how to do so in the next section. If you plan to use the software regularly in your work, however, you'll want to install it locally. There are two main strategies for setting up your system with Python, Jupyter, and the other libraries that you will probably want to use. The simple, one-stop-shopping approach is to download the Anaconda distribution, a large archive that contains Python, Jupyter, the scientific toolkit contained in SciPy, and more. This may be the most convenient approach to installation for Windows and Mac users, and is favored by many Linux users as well. I have worked with inexperienced users who were able to start working with Python on the Jupyter Notebook, on both Linux and MacOS, with very little fuss, by following the Anaconda route.

Others may prefer to retain more control, or may not require the entire Anaconda distribution since they have equivalent components, such as Python, already installed. And for users of other operating systems besides the big three, Anaconda is not available. These users will follow the second strategy. To install the software without using a monolithic distribution such as Anaconda, first make sure that Python (Python 3, unless you have a compelling case to use Python 2) is installed, and install pip, the Python package manager. The "pip3 install" command can then be used to install Jupyter, SciPy, and anything else from the Python universe. Jupyter may also be available from your distribution's package manager, but the version installed through pip is more likely to be up to date. This method allows you to experiment with a much smaller install of Python and Jupyter, and to install other components, such as SciPy, down the road, depending on your needs.

Once you've confirmed that Python is working on the command line, you can start up a Jupyter Notebook by executing the command "jupyter notebook" at the terminal. This will launch a local web server (that is only accessible to localhost by default), open a tab in your preferred web browser connected to the local server, and display a list of the files in your current directory. This web page will serve as a hub from which to open existing notebooks or start new ones, and to display information about running notebooks and shut them down if needed. The page will feature some tabs and menus as well; the most important when starting out is the "New" menu, shown selected in the figure below. Here you will see a list of your installed kernels. Python will always be available; on my machine, I've also installed the gnuplot kernel.

To create a new Python notebook, select the "Python 3" item, and a new tab or browser window will open, ready to accept input. The Jupyter notebook is organized into input and output "cells". You can type any legal Python code into the input cells, with the benefit of syntax highlighting and tab completion. Typing shift-return in an input cell evaluates the contents of the cell and displays the output in an output cell immediately beneath it. This output can consist of text, graphics, and more; the way it is displayed is partly controlled by global settings established in %-prefixed "magic" commands. The next figure shows an example of one of the magic commands, %matplotlib inline, that causes matplotlib plots to be embedded into the notebook.

Other magic commands do such things as define aliases for other commands, change aspects of the interface such as prompt colors and precision for printing numbers, manipulate environment variables, load code, log the session, search for objects in the current namespace, run system commands, time execution, and much more. These commands are specific to the kernel in use; kernels other than Python may provide a different set, or none at all. In addition to these, there are "cell magics," which alter the behavior of the notebook for a single cell. For example, if you begin a cell with %%markdown, the contents of that cell will be interpreted as markdown-formatted text, rather than Python code. If you have more than one kernel installed, you can send the contents of a particular cell to a different kernel by mentioning it in a cell magic, making the Jupyter notebook a multi-lingual computing environment. To find out about the other magic commands available, evaluate the command %magic.

Cells can be freely added, deleted and rearranged, gradually transforming a series of explorations into a narrative that teaches a lesson or recounts the development of a research program. As you work, your notebook is auto-saved at frequent intervals. You can also save a checkpoint at any time; the system places a list of your checkpoints in a menu, allowing you to revert the notebook to a previous state if you make a mess of it.

In my testing, Python programs run in the Jupyter notebook were able to handle anything that "normally" executed Python can handle, from file input and output to Turtle graphics to accepting input from the user, as shown in the figure to the right. The only significant difference from using the normal REPL is that the entire contents of a cell are sent to the interpreter upon pressing shift-return, rather than one line at a time.

The fact that everything seems to just work, as in the figure, where console input has been seamlessly translated into HTML and JavaScript, is an impressive achievement for which the Jupyter developers are to be congratulated. The occasional problem that I did encounter with the Python or other interpreter seeming to get stuck in an inconsistent state is quickly solved by selecting the menu command for restarting the kernel. There is another command that restarts the kernel and runs all the cells in the notebook, which is convenient for renumbering the input and output cells after a typical session of trial, error, and cell rearrangement; this also ensures that the code in all the cells still works, which makes sense to do before sharing your notebook. You will also need to restart the kernel if you want to reset any global state held by the interpreter.

If your interest is in using the notebook for education, you probably want to learn about ipywidgets. This is a library of interactive controls, implemented in JavaScript, that allow you, with very little extra code, to add a graphical interface to the Python code in the notebook. The widgets provide a way for the user to set function parameters and have the function re-evaluated and its output immediately displayed. The following short video shows the import necessary to use the widget library (it's in a separate cell, along with the numpy and pylab imports, as a reminder of the global state of the interpreter). The definition of a simple routine that plots the sine function of frequency n is in a separate cell. The single line of code in the next cell creates the widget and hooks it into the function. It has two arguments: the name of the function and the name of the function argument that we wish to control. If, as here, we set this to a tuple with three elements, these will become the minimum and maximum values of the argument and the step size.

This is the simplest example, showing how you can create a graphical interface to any function with a single line of code. The documentation in the link above introduces the other widgets available, for both input and display of data, facilities for laying them out into a more fully-realized graphical interface, and explains how to create your own custom widgets.

Sharing notebooks

Eventually, you may want to share your Jupyter notebook with colleagues or students. There are several strategies for accomplishing this; which one to choose is largely depends on your audience.

The native, auto-saved form of the notebook, which is in JSON format, can be opened and used by anyone with Jupyter installed (as well as any additional kernels or libraries that the notebook depends on, of course). This file is self-contained, with images included as inline data. If you're sharing among a group of colleagues who are also using Jupyter, there is little reason to do anything more elaborate; the textual form of the notebook file even makes collaboration using Git or another version control system practical.

If you need to provide a version of a notebook for reading only, with no interaction or modification required, you can export it. Simply by selecting a command from a menu, you can create a nicely formatted version of your notebook as HTML, PDF, or other formats. The result contains images and syntax-highlighted code, but omits any interactive widgets and their output.

This is the route to take in order to turn a notebook into an article or book. What really makes this possible is Jupyter's ability to insert markdown-formatted cells anywhere in the notebook. When these are "executed", they turn into the formatted, HTML version, but can be edited at will. Thus you can easily interleave formatted text with code and output to create a finished narrative.

For more control, such as the use of specialized templates, or for automating the conversion, the command "jupyter nbconvert" comes with the Jupyter installation. This command accepts arguments for output format and template; for some formats, such as LaTeX or PDF, you will need to have other software installed (pandoc for translating to LaTeX and some other formats, and a LaTeX installation for creating PDFs, for example).

The nbviewer project provides Jupyter's nbconvert facility as a web service. This is used by GitHub for displaying Jupyter notebooks; it converts the native notebook, on demand, into HTML. There can be significant delay when attempting to view a notebook served through nbviewer, but its use means that only the native format need be saved, which is useful for sites such as GitHub, where the user may want to select which commit of a notebook to view.

Exporting has the advantage that your reader can view your notebook without needing to install Jupyter (or anything else); only a web browser is required. In a fairly recent development, it is now possible to offer a fully interactive experience of your notebook while still requiring nothing besides a browser from the reader. The technology is called JupyterHub; it launches multiple instances of the Jupyter web server in response to requests from the public web, extending the capabilities of the local web server that runs on your machine in response to the "jupyter notebook" command.

An organization called Binder has adapted this technology to generously offer the public the ability to interact with Jupyter notebooks that are stored in GitHub repositories. In order to make your notebook available for interactive sharing, you merely need place it in a repository along with a simple text file that lists any imports required by your code. In order to use a notebook on GitHub, simply go to the Binder web site and enter the URL of the repository, and click on the orange "launch" button. A new browser window will open with the names of the files in the repository; click on the notebook of interest to launch it.

I've placed a simple notebook in a repository at https://github.com/leephillips/JupyterExperiments. It demonstrates the widget slider shown in the video above. If you launch it through Binder, you will see a list of the three files in the repository. Clicking on the name of the notebook, widgetExamples.ipynb, will launch it in a new window. Click on each cell and execute it with shift-enter to begin. You can make changes, add cells, and experiment at will, but if you want to preserve a copy of your work, you need to visit the "File" menu to download a copy to your machine. If you download as a "Notebook", you can open the file locally if you have Jupyter installed.

The other two files are a short README and the requirements.txt file, which tells Binder what the prerequisites are for running the notebook. This file can be more elaborate than my simple example, with version requirements and other information if needed.

The most recent release of the Jupyter Notebook is version 5.3.0, announced on January 17. While development of the mainline Notebook has and will continue for the foreseeable future, work is well underway on the "next generation" interface for Project Jupyter, called JupyterLab. It is still in "early preview" stage, but JupyterLab has already gained some enthusiastic early adopters. It retains the Jupyter Notebook web interface, but enhances it with improvements such as the ability to use multiple tabs, collapse cells, and edit markdown in side-by-side windows. JupyterLab also allows the user to interact with 3D objects and with large tables of data. As the interface is designed to be extended through the use of a public API, third-party developers will be free to create novel interfaces into the world of interactive computing and data analysis.

In just a few years, the Jupyter notebook has generated a great deal of enthusiasm and enjoyed widespread adoption. It is closely associated with SciPy, a free-software ecosystem for scientific and numerical calculation using Python, with which it has helped to accelerate the growth of a new culture of openness in the sciences. This is due, in part, to the ease with which Jupyter allows the researcher to create a living notebook describing methods and algorithms, and to easily share this document in a variety of forms. Jupyter provides a vibrant example of how a technology can transcend its origins as a mere tool, and have a powerful effect on the community that adopts it.

Comments (8 posted)