The mailing list for Linux kernel network development has moved from netdev@oss.sgi.com to netdev@vger.kernel.org
Details http://vger.kernel.org/vger-lists.html#netdev
(Also mentioned in the subscriber edition of LWN at http://lwn.net/Articles/139208/)
Thanks to Ralf Baechle and SGI for keeping the list going there for so many years.
One new feature in this kernel (2.6.12 final still seems some way off):
Finer-grained permissions for audit events. The kernel audit subsystem uses Netlink for communication with userspace. This communication includes:
Until now, Netlink communications were controlled under SELinux with the generic socket controls, and two special Netlink permissions: nlmsg_read and nlmsg_write. These permissions were used to determine whether Netlink messages, from userspace, were essentially either read or write operations. For example, listing the kernel routing table requires nlmsg_read permission for the netlink_route_socket class, but writing to it requires nlmsg_write. These two permissions provide a great deal of flexibility and control over user-kernel communication. They’re also abstracted in a simple way, “read” and “write”, with only the latter generally being considered privileged.
However, the audit subsystem has some very specific requirements based on CAPP (Controlled Access Protection Profile), where audit records need to be reliably and sequentially correlated with specific login sessions. As the kernel audit code is the source of truth for audit records, login events are sent to the kernel, allocated a sequence number then passed back to userland (typically to auditd), all via Netlink. This messaging did not fit the existing SELinux Netlink permissions, as it is not about reading or writing privileged kernel data.
Another issue arose where the listing the kernel audit rules is considered a privileged operation by the audit folk.
So, two new permissions have now been added for the netlink_audit_socket class:
| nlmsg_relay | Controls transmission of AUDIT_USER messages, which contain login data and are relayed back to userspace. |
| nlmsg_readpriv | Controls transmission of AUDIT_LIST messages, which request listings of kernel audit rules. |
These permissions may be useful to other classes of Netlink sockets, but are currently only valid for audit.
Other fixes in this kernel: Stephen Smalley cleaned up some of the SELinux IPC code, and Herbert Xu fixed an oops in the SELinux IPv6 packet parsing code.
A few more SELinux kernel patches have been merged since 2.6.12-rc2 and are now available in -rc3:
avc: denied { create } for scontext=system_u:system_r:hald_t
tcontext=system_u:system_r:hald_t
tclass=netlink_kobject_uevent_socket
With Linus’ kernel at -rc2 stage, we now have a reasonable idea of what 2.6.12 will look like. Here’s an overview of SELinux kernel features which have been added since 2.6.11.
name_connect
This is a new permission for the TCP socket class, specified by Dan Walsh and implemented by Stephen Smalley. It extends the way SELinux handles the connect(2) syscall for TCP sockets. The existing SELinux connect permission is applied to all classes of sockets, simply determining whether a domain is allowed to use the connect(2) syscall on the specified socket class. With name_connect, SELinux makes an additional check as to whether the domain can connect to a specific set of port types. Here are some examples from current policy sources:
allow mount_t portmap_port_t:tcp_socket name_connect;
allow squid_t { http_port_t http_cache_port_t }:tcp_socket name_connect;
allow unconfined_t port_type:tcp_socket name_connect;
The first is the simplest case, where a domain needs to connect to one type of port. In this case, the mount_t domain is allowed to initiate TCP connections to ports of portmap_port_t type. The latter is defined in policy as port 111 via the portcon directive. This allows the mount_t domain to perform portmap queries over TCP when mounting NFS partitions.
Importantly, as SELinux denies everything by default, allowing only what’s explicitly specified, the mount_t domain can’t connect to any other types of port.
In the second example, we see how the policy language supports multiple port types: the squid_t domain is allowed to initiate connections to ports of type http_port_t and http_cache_port_t.
A catch-all entry is shown last, for the unconfined_t domain. In this case, the port_type attribute is used to signify all port types. This is useful if you don’t know what ports a domain will need, or haven’t yet analyzed the needs of the domain — assuming you prefer it to work correctly rather than not at all.
In terms of the implementation, some thought was given to extending the existing packet-level controls, recv_msg and send_msg, to detect whether a TCP packet has a SYN bit set. This approach would have required adding significant complexity and per-packet processing overhead to the SELinux code; been potentially difficult to support extensibly with the existing policy language; and replicated existing iptables functionality. And as we’re only concerned with outgoing stream connections and the associated local process, it turned out better to place the hook at the socket level. This was done by adding some TCP specific code to the existing selinux_socket_connect hook, called during connect(2), via the LSM security_socket_connect hook. No core kernel code was modified.
The name_connect permission should help lock down a lot of the networking policy. For example, domains which need networking also tend to need to perform DNS lookups. The new permission will allow domains to be locked down to only outgoing DNS (in the TCP case) and whatever else they actually need. This kind of fine grained control should help prevent some common network security problems, such as compromised systems being used to send spam. If, say, Apache is compromised via a remote hole, SELinux can still lock down the network resources used by the application at the kernel level. In this case, with name_connect, it’s quite simple: domains which need to initiate TCP connections to port 25 are provided with the permission, all others are denied by default.
reiserfs
Previously, SELinux file labeling for reiserfs via xattrs has been seriously broken, as described in this mailing list post. The problem was that reiserfs maintains internal inodes, which the VFS and thus SELinux were not distinctly aware of, leading to problems such as a deadlock between reiserfs and SELinux when reiserfs creates internal inodes for storing xattr data. This issue was solved by Jeff Mahoney of Suse, who added an S_PRIVATE flag to mark inodes as internal to the filesystem. This flag signals to the LSM framework (and its applications, such as SELinux) that access control for the inode will be handled internally by the low-level filesystem code.
It appears to be working well now, although I’m not sure how much testing coverage it’s had. Currently, standard SELinux policy disables the use of xattrs for reiserfs, so if you want to try it out, you’ll need to edit policy sources:
# reiserfs - until xattr security support works properly #genfscon reiserfs / system_u:object_r:nfs_t
fs_use_xattr reiserfs system_u:object_r:fs_t;
Build, then load the policy (and install it if you wish to keep using it). When mounting any reiserfs partitions after this, you should see the following type of kernel log message:
SELinux: initialized (dev hda3, type reiserfs), uses xattr
The “uses xattr” clause shows that xattr labeling is active on the partition (which will need labeling if it’s never been labeled before). If you intend to keep using reiserfs with SELinux xattrs before your distro fully supports it, you’ll also need to update the policy Makefile so that reiserfs is included in the FILESYSTEMS variable, and also make similar changes to the fixfiles script.
Enhanced MLS
Multi-level security (MLS) is typically used by military and government folk who need to manage information at different security levels, and handle users with varying security clearances. SELinux has always had rudimentary and experimental MLS support, although I don’t believe it’s ever had much use. A company called Trusted Computer Solutions (TCS) has been working on a more flexible and fully featured MLS implementation for SELinux, and an initial patch of theirs is now in the upstream kernel. It updates the core MLS implementation, replacing hard-coded logic with a more flexible and expressive system based on policy language constraints. The patch also allows MLS to be enabled at boot-time (like SELinux itself), and supports a single policy binary format for MLS and non-MLS systems.
Chad Hanson gave a talk on their work at the recent SELinux symposium, slides of which may be downloaded here. MLS under SELinux is still incomplete, lacking features such as polyinstantiated directories, and somewhat experimental. If you’re feeling brave, you can try setting up an MLS system with the new TCS code by following the README.MLS in the latest selinux-doc package. It’s probably best to try this on a system which you don’t mind reinstalling from scratch if something goes wrong.
Memory protection checking for legacy binaries & libraries
In recent kernels, when a process maps a memory region (or changes its protection), the requested protection flags may be modified by the kernel before access control checks are performed. This currently happens if a binary or shared library is marked as needing an executable stack, and PROT_READ is requested. In this case, the kernel will also add PROT_EXEC (“read-implies-exec”). With this behavior, SELinux policy for some applications had to be loosened to allow execution privileges when they may not have really been required (e.g. an application isn’t marked at all and the kernel assumes it needs an executable stack).
To address this, Stephen Smalley implemented a way to control whether SELinux uses the protection that the kernel will apply, or the protection originally requested by the application. An selinuxfs node has been added, checkreqprot, which allows selection of the required SELinux behavior by writing one of the following values to it:
0 – SELinux uses the protection value to be applied by the kernel.
1 – SELinux uses the protection value originally requested by the application.
The current value may be viewed simply with:
# cat /selinux/checkreqprot 1
The default value may be set during kernel compilation via the SECURITY_SELINUX_CHECKREQPROT_VALUE parameter.
Miscellaneous
SELinux now logs the details of any Netlink messages it doesn’t understand, to handle the case where new message types are added and the SELinux code is not updated. Such messages are now also allowed through if in permissive mode.
The SELinux boot options have been documented in the kernel source tree, as requested by Andrew Morton.
Code which handles writes to the /proc/<pid>/attr nodes has been modified to treat a newline character as a null value. The normal way to clear these nodes of any value is to do an empty write, but Posix says that this can be ignored and we can’t rely on that behavior. So, thanks to Posix, you can now clear the value of a procattr node by writing a newline to it. This also allows easier modification of the nodes from shell scripts, but direct manipulation of these nodes should not normally performed: use libselinux and helper utilities instead.
Note that these changes are now available in Fedora rawhide kernels (and likely other distributions’ development pools tracking Linus’ kernel). If you update the kernel, make sure you also update your SELinux policy, as older policies will not have any allow rules for the name_connect permission and you could find your system somewhat more secure than you intended.
The Lions’ Commentary finally arrived. After weeks of waiting with one of the large online booksellers, they canceled the order. So I emailed the publisher, Peer to Peer Communications, and they suggested buying from Lulu, which worked out well. A colleague had exactly the same experience.
The SELinux Symposium in Maryland was very well attended. Slides from the talks are available now here. It’s good to see such a high level of interest displayed on a project that you’ve been working on for years. At this stage it seems that most of the interest is from government related folk, and not yet the wider enterprise or general user communities. (Although there does seem to be broader involvement in Japan).
One of the challenges for the SELinux project now, I feel, is to gain more traction with the wider community. After chatting with some people at the symposium, I’ve got a few ideas for progress in this area.
Another critical factor is the evolution of the SELinux toolchain, particularly relating to policy management. Looks like there’s some good fundamental work going on here.
Enhancing the security of the desktop is a major challenge. Colin Walters presented a good overview of the problem space and provided some examples of work he’s been doing, while Jim Gettys held a BoF session on Security Enhanced X (not sure if there are any notes from this available). Desktop SELinux integration is definitely an area that someone looking to make a mark in the open source world should have a look at, it’s fertile and somewhat unexplored ground, and there are some very highly experienced people likely available to mentor.
Lions’ Commentary on UNIX is being published again by Peer to Peer Communications. Details here.
This famous 70’s commentary on the Unix source code is considered by many to be the best text on the subject. It was innovative in presenting remarkably well annotated source code, an unusual thing at the time. Originally written as a text for a UNSW course, the book was not officially published for some 20 years, during which time it became what is believed to be the most copied book in the computing field. It went out of print last year (I think), just before I tried to buy a copy. I’m glad it’s available again so I can finally own a “real” version. Used copies of this 1996 version are selling for around US$170 at the moment, although I guess these prices will drop very soon. I have no idea how much one of the original Bell Labs versions would go for, if you can even find one.
Note that Greg Lehey has put the source and PDF/PS versions of the book online here, as found in an alt.folklore.computers posting from 1994. This was from before the original official publication in 1996 and does not contain the extra commentary on the book itself by folk such as Dennis Ritchie and Ken Thompson.
Poking around a little, I found this 1994 interview with John Lions reposted to Usenet, which shows that the students at UNSW actually suggested covering the entire kernel, after initially only having parts of it presented to them. The interview is also interesting for some general perspectives on Unix.
I’ve heard a greybeard say that the best thing about the Lions book is that you can use it to fit an understanding of an entire Unix kernel into your head. Trying to understand, say, all of the Linux kernel these days is likely an impossible task: it’s just too big and complicated. And, judging by the Linux kernel over the last few years, things are changing very quickly, at an increasing rate (I’m reminded of the accelerating expansion of the Universe :-) So, I think there is really great value in a book such as this, covering an early, classic kernel, as a foundation for a fuller understanding of modern kernels.
Peer to Peer are also about to release an interesting looking book titled Building the ARPANET, a collection of seminal papers and documents on the subject. For those of us interested in such things, this should be a great way to access the information. I often spend quite a bit of time trying to track down a paper that I’m fond of, such as IEN 2, “Comments on Internet Protocol and TCP” by Postel 1977, which outlined the concept of separating a “hop by hop” interface from TCP, creating what we now call the IP layer.
We are screwing up in our design of internet protocols by violating the principle of layering. Specifically we are trying to use TCP to do two things: serve as a host level end to end protocol, and to serve as an internet packaging and routing protocol. These two things should be provided in a layered and modular way. I suggest that a new distinct internetwork protocol is needed, and that TCP be used strictly as a host level end to end protocol.
Cool stuff. I look forward to a book collating the best of this kind of material from the ancient era.
I’d also like to see something similar collecting together seminal computer security texts, particularly those now out of print and held tightly in rare public copies of journals by a few libraries. Examples are found in proceedings of the National Computer Security Conference, such as Boebert & Kain’s A Practical Alternative to Hierarchical Integrity Policies from 1985, which outlines the concepts of Type Enforcement, a central component of SELinux.
NIST is making an effort in this area. They’ve published all of the proceedings of the NISSC (initially NCSC) from 1996 to the final conference in 2000 here. My understanding is that copyright problems are preventing online publication of proceedings from earlier years (where you would find the Boebert & Kain paper), although they’ve put up selection of important earlier papers on their History of Security page. While people have written excellent textbooks covering these topics in a readable and contextualized manner, I still like reading the original papers where possible.
I’ve placed a copy of my January 2005 Linux Journal article online: Networking in NSA Security-Enhanced Linux. Thanks to Don Marti for making the copy edited, HTML formatted version available.
I’ll cover some of this material in a talk at the SELinux Symposium in March.
Introduction
This article covers some recent changes in the SELinux kernel code including a performance patch from Kaigai Kohei of NEC and related updates to the selinuxfs API. Currently, these changes are waiting in the -mm tree for merging into Linus’ kernel in 2.6.10, and are also available in the development Fedora and RHEL4 Beta kernels. This article should be useful to sysadmins who are looking to understand SELinux performance and generally also to curious people.
Background
Until now, SELinux kernel development has been focused primarily on getting the code merged into the upstream kernel and preparation for integration into mainstream Linux distributions. This has taken several years, from the initial release in 2000 where SELinux was a patch against the kernel, to the port to the LSM framework, upstream merge and integration work performed by various distributions including Debian, Red Hat and Gentoo.
During this phase of the project, performance tuning had not received much attention from developers. While the general base performance hit of SELinux is around 7% — which is not too bad — testing on large systems revealed serious scalability issues.
AVC operation and analysis
To understand this, here’s a brief explanation of how the core of the SELinux code works. SELinux uses a series of hooks (via LSM) at strategic points within the kernel. These hooks are used to divert the normal flow of the kernel into a security checking mechanism called the Access Vector Cache (AVC). The AVC contains cached permission checks performed against the system’s security policy. As the working set of permission checks for a given workload is typically quite small, having them cached allows SELinux to scale virtually independently to the size of the security policy. For the vast majority of cases, an SELinux permission check is a quick cache lookup rather than a search of the entire security policy database.
This sounds great except that the AVC was protected by a global spinlock. Additionally, due to the fact that SELinux hooks can be called from hard interrupt context, interrupts had to be disabled and interrupt state saved before taking the lock, then resumed on release (i.e the spin_lock_irqsave/restore() variant was used). This is quite expensive and the lock showed up clearly in profiling runs.
Further analysis revealed that it was trivially possible to generate hundreds of thousands of AVC lookups a second on reasonably modest hardware (e.g. running ls -lR /usr twice), and the atomic operations associated with spinlocks alone were clearly hurting SMP performance.
Solution: RCU
A few attempts had been made at “fixing” or getting rid of the AVC lock, using reader/writer lock variants and per-cpu techniques. Neither worked very well. Kaigai’s patch, however, utilized RCU, a mechanism which allows lockless reads and the elimination of atomic operations in read paths. As the AVC is overwhelmingly read-only on a typical system, RCU turned out to be an ideal method for removing the AVC lock completely.
With the RCU patch applied, SELinux scalability problems noticed in several benchmarks were eliminated. The benchmark results can be found in this post to lkml. For example, Kaigai measured linear scalability for the dbench benchmark on a 32-way system.
Some minor tradeoffs in baseline performance showed up in some benchmarks, although the scalability win definitely outweighs these (if they are even noticeable to anyone in the real world).
The RCU patch does not solve all of the SELinux performance issues. For example, some networking hooks do not use the AVC and effectively always fall through to security policy lookups, which involves the use of a global spinlock. Work is ongoing in these cases and they should be similarly resolved with caching and RCU reasonably soon.
Further improvements?
During development and analysis, I instrumented the AVC code and enabled some of the internal debugging code to get a better look at what was really going on and see if there were any further improvements to be made. (Much of this instrumentation is now available via selinuxfs, and is discussed below). Firstly, I was surprised to see that the AVC seemed to be thrashing. The cache had a maximum size of 410 entries (I don’t know where this specific number comes from :-). When more than this number of entries was needed, the AVC code used an LRU policy to reclaim cache entries in chunks. It seemed that this would surely be bad for performance, given that I was seeing thousands of AVC entries being used in total. Additionally, there were 512 hash buckets for the cache, which meant that at least 102 buckets would not be used. My thoughts were to increase the maximum cache size to reduce the need to reclaim entries, and then implement a periodic garbage collector (GC) to keep the hash chains short. Shortening the hash chains was potentially important as some workload (such as bootup) can invoke thousands of AVC entries which are then not used again or used very infrequently from then on.
The first step in implementing the GC was to add a last used timestamp to each AVC entry. This was accomplished by setting a field in the AVC node structure to the current value of jiffies, the global current tick count. Then, from a timer, the GC cleanup code would traverse the cache, looking for AVC entries older than a certain amount of time (really, ticks converted to time). As the GC would run extremely infrequently compared to the AVC lookups (many orders of magnitude), the GC run itself should not cause any undue performance problems. And it didn’t, although it turned out that the GC system was still somehow hurting performance. The problem with the GC turned out to be reading the global jiffies variable on each AVC lookup. It is declared volatile (which kills some possible optimizations by the compiler) and as a constantly updated global value, reading it very frequently incurs significant overhead on a heavily loaded SMP system.
So, the GC idea was dropped, and the default value for the maximum size of the AVC cache was increased to allow it to fill up all of its hash buckets. Extensive benchmarking with various values showed 512 to be a good choice.
But what about the cache thrashing? After further analysis, this also turned out to be bogus. Using the instrumentation, I was able to observe that workloads tend to use a surprisingly small working set of AVC entries. Most of the cache entries were stale or infrequently used, so reclaiming them was not generally a problem. To keep an idle system running, with SSH and a monitoring script active, as little as 20 or 30 AVC entries might be in the working set. And perhaps that number again if running a simple server workload such as Apache with static content. It was difficult to find a real workload which used more than a hundred AVC entries in a working set. With the original reclamation code, if the cache was populated with mostly stale entries (e.g. those created during a login or daemon startup), and a new workload was started, there would be an initial hit while the LRU based system reclaimed enough entries for the new workload, but this would then be amortized very quickly over the life of the workload. So, the original design was fine all along. Lesson: be careful about second-guessing NSA code :-)
The new AVC API
One thing that seemed useful though would be to allow the sysadmin to control the maximum size of the AVC, so that complex, multiple or fast changing workloads could be more readily accommodated if needed. This is now a tunable exposed via the selinuxfs API.
To view the current value:
# cat /selinux/avc/cache_threshold 512
To set a new value:
# echo 1024 > /selinux/avc/cache_threshold
I would suggest always verifying that this succeed, as the new setsecparam permission is needed to write to the file.
It’s not much use providing a way to modify the maximum cache size without some way to monitor the operation of the AVC. Two further files have been added under the avc directory:# cat /selinux/avc/hash_stats entries: 503 buckets used: 269/512 longest chain: 5
This is really to help debug complicated performance problems, although it is worth explaining. The output shows the total number of AVC entries, hash bucket distribution and longest hash chain length. Maximum chain lengths should generally be quite short (less than 10 is typical on my systems). Significantly large values indicate possible performance issues, as the AVC may be spending a lot of time traversing long hash chains on each AVC lookup. In this case, performance may improve by reducing the size of the cache, although it might be worth posting a report to one of the SELinux mailing lists if you see anything odd here.
# cat /selinux/avc/cache_stats lookups hits misses allocations reclaims frees 933871 928520 5351 5486 1216 5124 723798 719270 4528 4569 608 4483 1677626 1675464 2162 2180 352 2051 1390072 1388430 1642 1671 576 1744
These are per-cpu statistics for various AVC operations and hopefully fairly self explanatory. The lookups field is a good indicator of the load being placed on the AVC. The field to watch, probably, is reclaims. This is a count of the current total number of reclaimed cache entries. If it keeps changing, you may need to increase the cache size. Generally it is normal to see light reclaim activity from time to time.
The avcstat utility
Note that you probably should not just cat this file directly. Use the avcstat utility available here or in the latest libselinux package (Fedora users can just update to the latest development stuff via yum and it will all be there). This utility is similar to tools such as vmstat. It adds up the per-cpu values and displays them in a tabular format. You can display continuous values by including the number of seconds between updates on the command line:
# avcstat 1
lookups hits misses allocs reclaims frees
4782948 4769221 13727 14013 2752 13465
81 81 0 0 0 0
47 47 0 0 0 0
53 53 0 0 0 0
^C
The first line always shows the current total, then by default, shows relative values. Using the -c switch shows cumulative values, if desired.
Conclusions
The use of RCU solved a serious scalability problem with the AVC, thanks to the work of Kaigai and the RCU developers. It seems likely to be a useful approach for dealing with similar problems, and specifically with some of the SELinux networking code as mentioned. The new AVC API and avcstat utility should prove useful to sysadmins and SELinux developers who need to analyze and tune performance. Feedback from users is welcome. These are new features which have not had wide exposure and there are obviously going to be many workload which I’ve not tested. If you have any interesting performance situations, please post some information and output from the AVC API to one of the SELinux mailing lists.
I’ve been trying to read Introduction to Quantum Computation and Information, a collection of papers on the subject used as an introduction to the field. I can’t claim to understand it, but there are some interesting parts nonetheless.
One is an example of Quantum Cryptology in the form of Quantum Money, a theoretical idea which could prevent counterfeiting by storing sequences of photons within banknotes, along with a serial number. The photons would be randomly polarized during printing, and the bank would keep a secret record of photon polarizations for each banknote. It would be infeasible to copy the banknotes, as measuring unknown quantum states disturbs the states irreversibly. As the bank knows the quantum states within each banknote, it can determine whether the banknote is a copy. This is a little simplified, but you get the idea.
Anyway, such an idea is not amazing today, but the theory for this was developed in 1970 or so by Stephen Weisner, who mysteriously did not publish it until 1983. Apparently his ideas were way ahead of their time and only taken up later, for example, by scientists who published the first known Quantum Key Distribution (QKD) system in 1984. The first working QKD was first demonstrated in 1989, and the first network protected by quantum cryptography was deployed only this year.
Arnaldo is one of the core kernel networking developers who has been heroically modernizing implementations of legacy protocols within the networking stack. Where else can you find fully threaded implementations of DDP, LLC, X.25 and IPX?
So, today, I was a little perturbed to see him connecting to IRC via IPv6, at last. Does this mean that IPv6 is now a legacy protocol? :-)