Kernel Traffic #65 For 1 May 2000

I have some precision on the O(...) notation -- if you care ;-) It is due to the Russian mathematician Landau, and is widely used in mathematics (function analysis). It comes in two flavor:

• o(f(n)) -- we pronounced it "little o" in French, I don't know the US name. Briefly, a function f1 is said to belong to o(f2(n)) if the limit of f1(n)/f2(n) is zero when n increases to infinity.
• O(f(n)) -- we pronounce that "big O" around here. Same principle, but the limit is an arbitrary, non null constant.

What does it mean in practice -- applied to computer science?

A function that belongs to o(f(n)) has a cost which is negligible compared to f when n gets large. A function that belongs to O(f(n)) has a cost which is similar to f when n gets large enough.

Examples:

• functions in O(1) are constant time (or cost), independent of n;
• functions in O(n) have a linear cost with respect to n when n gets large;
• O(n^2) is quadratic, etc.

Note that this is true *for large values of n*, and that the constant implied by the O(...) notation is *arbitrary*. So for small value of n, a function which is O(n^2) might be much faster than an O(1) function.

just to let everyone know - I tried the kdb-v1.1-2.3.48 from SGI www.oss.sgi.com against 2.3.99-pre6-3 on SMP and it works just fine (the modifications I had to make were trivial).

It definitely didn't work against 2.3.49-52 but that may have been a different kernel bug triggered by kdb. (on a different SMP machine)

How do people feel about the following proposal:

Adding support for login user id (auditable user id).

1. adding a variable "luid" to the uid_t line in the task struct
2. adding two system calls - 1 to 'set' and one to 'get' the value.
3. adding CAP_SET_LUID that allows setting setting the luid.

Set points would be at 'login', cron/at (running as a user), r(sh,cp,login), and s(sh,..?). Implementation at user level would probably be in a pam library. This wouldn't change over exec's/forks nor would it change at with 'su' nor with SUID programs.

This id would be used to track a user from the point of access to the system to their ending contact which is required for C2 (now CAPP) auditing.

Ok, but what's the point? There is a perfectly functional "real user id", and since you have to audit daemons to ensure LUID is properly tracked according to your preferred definition of "session", why not just ensure that the ruid tracks the same way. I.e., just use ruid and call it LUID for CAPP purposes.

If you're thinking about capabilities to restrict LUID changes to the select few daemons (e.g. just "login" and then only via a physical console) -- well, once you've gone that far, the ruid isn't used for anything else. It's available for use as the CAPP LUID :-)

No. ruid changes over su; it has to, so setuid programs do the right thing (if you su, you do not want setuid programs to switch between their set uid and your original real uid). You need a separate uid to track who you logged in as for security auditing.

Also, CAPP/C2 security auditing/logging doesn't work in terms of sessions. LUID isn't set by login to enforce some kind of session mechanism, but solely to indicate that some process which does something security-auditable was ultimately initiated, directly or indirectly, by a user who authenticated to the system as the user with that (l)uid. Cron also sets it for cron jobs, because it's acting as a proxy to run things for the user that installed the crontab.

These are some basics from CAPP that may explain

The Common Criteria (CC) Controlled Access Protection Profile, hereafter called CAPP, specifies a set of security functional and assurance requirements for Information Technology (IT) products. CAPP-conformant products support access controls that are capable of enforcing access limitations on individual users and data objects. CAPP-conformant products also provide an audit capability which records the security-relevant events which occur within the system. The CAPP provides for a level of protection which is appropriate for an assumed non-hostile and well-managed user community requiring protection against threats of inadvertent or casual attempts to breach the system security. The profile is not intended to be applicable to circumstances in which protection is required against determined attempts by hostile and well funded attackers to breach system security. The CAPP does not fully address the threats posed by malicious system development or administrative personnel. CAPP-conformant products are suitable for use in both commercial and government environments.

...

The CAPP is for a generalized environment with a moderate level of risk to the assets. The assurance requirements and the minimum strength of function were chosen to be consistent with that level of risk. The assurance level is EAL 3 and the minimum strength of function is SOF-medium.

...

TERMS:

An _authorized_user_ is a user who has been properly identified and authenticated. These users are con-sidered to be legitimate users of the TOE.

An _authorized_administrator_ is an authorized user who has been granted the authority to manage the TOE. These users are expected to use this authority only in the manner prescribed by the guidance given them.

...

All individual users are assigned a unique identifier. This identifier supports individual accountability. The TSF authenticates the claimed identity of the user before allowing the user to perform any actions that require TSF mediation, other than actions which aid an authorized user in gaining access to the TOE.

The LUID concept is meant to address the needs of a particular multi-national security specification (the Common Criteria). The countries that co-developed the Criteria are: the UK, France, Germany, Canada, Netherlands and the US. It has been agreed that a CC system evaluated in 1 country will be accepted in the other 5 countries.

Find the complete document on page http://www.radium.ncsc.mil/tpep/library/protection_profiles/index.html. The latest Common Criteria documents can be found at http://commoncriteria.org.

It is my reading of the above that a CAPP system would not be attached to the internet but only a local 'intranet' composed of other similarly controlled systems.

This certainly isn't meant to be a be-all, end-all answer to security. This is a first step for a well defined environment (like a corporate intranet.

A CAPP compliant system meets "Evaluation Assurance Level 3" which describes (in exhaustive detail) the level of testing and proof of Assurance. It is *not* a formal mathematical proof of correctness (EAL7). For more on EAL's, see page http://commoncriteria.org/docs/index.html, Document CCV2.1, Part 3.

CAPP compliant systems are thought to be the minimum security needed for many commercial vendors and will be the minimum requirement DoD systems next year. These are not firewall system and unlikely to be used out of an 'internal environment'.

Hm. CAPP appears to have altered goals from C2: C2 was to detect *internal* security breaches on an assumed-externally-secure system, and indeed its auditing provisions are not suitable for detection of external threats.

If CAPP truly targets external threats, then I think we should indeed bypass it as a completely misdesigned system for such.

C2, from which CAPP is descended, explicitly *does not cover* networked systems. Not even "intranet"-connected systems. C2 would need a major reworking to even begin to address such.

I am starting to agree that CAPP is a trainwreck....

I will concede the point about LUIDs per se; it looks like CAPP has generalized them somewhat. However, keep in mind that the more complex the mapping of a user identity, the more suspect it is from an auditing standpoint.

The PPPOX code certainly seems to be a good framework for PPPoE and similar, where some new and somewhat complex ppp-specific encapsulation methods for ppp frames are needed. But for tunneling ppp over existing protocols, where the additional ppp-related encapsulation is simple, maybe another approach might be more appropriate.

I've started to implement ppp over the AF_X25 socket layer. Here, ppp frames are carried directly inside the X.25 payload, without any additional encapsulation headers. The RFCs for ppp over other protocols are frequently similar (no additional ppp frame encapsulations or just some pad bytes). For such protocols, the encapsulation of the ppp frames is trivial and the PPPOX framework (which makes the task of implementing complex ppp encapsulations schemes more easy), does not give any advantage. Instead, the hard problems faced when interfacing such a protocol to ppp are the interactions with the protocol internals. Existing network protocol stacks differ in various areas (e.g. which parts of the protocol processing need process context, how can ppp_channel flow control be interfaced to the carrier protocol's flow control mechanism).

Thus, the design chosen is a library approach, providing services which make interfacing of existing socket code to the ppp_generic code as well as to generic tunnel network interfaces (e.g raw-IP on top of X.25 payload) easy. It aims beeing re-usable for other protocol stacks.

Currently, I've just finished the design and some of the prototype coding, but totally untested until now. Thus, I did not upload it yet. But If you (or soembody else) is interested to have a look at the prototype code (I don't know whether this or the PPPOX approach will be more appropriate for your PPPoATM), please drop me a mail.

Some of us are trying to maintain drivers that are being used both in 2.2.x and 2.3.x - having the compatibillity code stripped out regularly from someone making a quick hack in the 2.3.x tree is a major pain.

Dropping 1.2.x support is very reasonable and 2.0.x is certainly debatable, but if an author is actively maintaining the code, it should be up to him/her to decide.

No.

It's a major pain just because you do it wrong.

A lot of network drivers have this bass-ackwards way of maintaining both 2.3.x and 2.2.x drivers- they do something like

#ifdef LINUX_VERSION_CODE > 0x20139

struct net_device_stats stats;

#else

struct enet_statistics stats;

#endif

or something like

#if (LINUX_VERSION_CODE < 0x02030d)

dev->base_addr = pdev->base_address[0];

#else

dev->base_addr = pdev->resource[0].start;

#endif

and they do this in the middle of code that makes it fairly unreadable.

And then people complain when 2.3.x cleans stuff up, and removes those stupid things. Without realizing that the cleaned up version is often much better, and _can_ be made to work with the older kernels too.

What you can much more cleanly do in almost all cases is to have a "forwards compatibility" layer, so that you can write the driver for the current code, and then still be able to compile it for 2.2.x. And that forwards compatibility code doesn't even need to be in the recent kernels: after all, it is really only needed on the =old= setups.

Why do it that way? The BIG reason for doing it this way is that by putting the compatibility code into _old_ kernels when supporting a driver like that, you don't perpetuate the code. It automatically and magically just gets dropped whenever people don't care enough about older versions, because it's not carried around in the new code.

Example of how this _can_ be done (network drivers are the best example, simply because there are so many of them, and because there are some recent changes to how they operate that people still remember):

• use the new operations everywhere. That means using netif_wake_queue()/netif_stop_queue()/etc WITHOUT any #ifdef's. They =do= work on 2.2.x too, with minimal glue (and that glue should be maintained in the 2.2.x tree, not in the 2.3.x tree!)
• use things like "pci_resource_start()" which have been added explicitly to make it easier to do certain backport things. It's defined in 2.3.x, and not defined in 2.2.x, but again you can have trivial backwards compatibility glue to take care of the issue. And again, the compatibility crud goes into the _old_ tree.

So for example, the backwards compatibility crud in 2.2.x (which doesn't even need #ifdef's, because it only exists in 2.2.x) would look something like:

#define net_device device
#define net_device_stats enet_statistics
#define dev_kfree_skb_irq(a) dev_kfree_skb(a)
#define netif_wake_queue(dev) clear_bit(0, &dev->tbusy)
#define netif_stop_queue(dev) set_bit(0, &dev->tbusy)
#define netif_queue_stopped(dev) ((dev)->tbusy != 0)
#define netif_running(dev) ((dev)->start != 0) static inline void netif_start_queue(struct net_device *dev)
{

dev->tbusy = 0;
dev-<start = 1;

}
#define pci_resource_start(dev,bar) ((dev)->resource[(bar)]&PCI_BASE_ADDRESS_MEM_MASK)
#define module_init(x) ...

and you're now almost done. With a clean driver, and without any #ifdef's AT ALL.

(Yes, there are still going to be details, but you're getting the picture on how this should work).

Now, one argument is commonly that "but you can't change old kernels, so the old kernels cannot have new interfaces added to them when a development kernel changes". And that argument is _bogus_. Because if you truly don't change old kernels, then you also don't need to have any backwards compatibility AT ALL, because the old driver will obviously continue to work (or not work) forever unchanged.

This is why I do not want to add compatibility files to development kernels. It's the wrogn thing to do, because adding compatibility files to new kernels always implies carrying baggage around forever. Adding the compatibility files to old kernels is conceptually the right thing to do: it tells you (in the right place) that old kernels are still maintained.

No. Wrong moral. You should not "fix" MIN().

MIN() is a _bad_ thing to use. It _always_ gets the sign wrong. Sorry, but that's how it is. It makes people think that "oh, it takes the minimum of two numbers" and at the same time it makes people completely forget signedness issues.

In short, it's a really stupid macro, for something that is usually simpler to do by hand anyway. And doing it by hand you can make it work right, without confusion like this.

MIN() should go. If people really want to use a macro for something as simple as MIN(), then you should always use UMIN() and SMIN(), and make people have to think about signedness issues (but even then you tend to be better off just doing it explicitly by hand).

This one doesn't get it wrong:

#define min(x, y) ({typeof (x) x_ = (x); typeof (y) y_ = (y); x_ < y_ ? x_ : y_;})

The variables x_ and y_ are the _same_ types as the x and y the macro gets, the sizeof-ish behaviour of typeof ensures no evaluation of the expression (i.e., no side effects); and then it does the comparison as it would with the original values, just never evaluating anything twice. No (explicit) mess with temporaries that have to be declared, and no huge expressions that have to be written twice (only to get one of them wrong, as Murphy's law assures will happen where you can't see it).

please consider the following patch (against 2.3.99-pre3) or a similar thing for inclusion into the kernel. It fixes the long-standing problem of finding out the right compiler options to compile external modules.

This patch causes "make dep" to write a makefile fragment which can be included from a module makefile.

Just a quick heads up that I haven't had access to a computer for two days (and yes, my hands _are_ shaking), because we're in the middle of a move. We've gotten everything but the cats to the new house, but all our stuff is still in big boxes, and I will probably remain unable to read email from home for at least another week.

So this is just a notice to people to not worry - I'm just snowed in and will probably require some re-sends after it all clears up..

for several months I had the problem that access to some web sites fails mysteriously. This means I never got a reply although the servers were reachable with ping and telnet.

Today I did

echo 1 > /proc/sys/net/ipv4/ip_no_pmtu_disc

and suddenly all these sites worked again for me. I use kernel 2.2.x (2.2.pre15-19 currently). Some of the affected sites are dri.sourceforge.net (in fact, the whole sourceforge.net) and support.3com.com

Are these web sites broken?

Actually, yes, the web sites are broken; but it's a relatively subtle problem. Here's what's going on.

The web sites are probably behind a firewall which is filtering all ICMP packets (since some dumb firewall administrator read somewhere that all ICMP packets are evil). Somewhere in the network path between you and the web site, there's a link which has a maximum MTU which is smaller than the ethernet default of 1500 bytes.

Normally, dumb hosts would just send bytes using their local max MTU, and then when the packets hit the link with the restricted MTU, the packet would get fragmented at that point, and then it would get reassembled at the receiver. Fragmentation has the problem, though, that it only takes one fragment to get lost in order to require the retranmission of the entire packet, thus wasting network bandwidth --- and if the reason why the one of the fragments was dropped was due to link congestion, the fact that all of the fragments have to get retransmitted can actually worsen the situation.

Hence, good network citizens (of which Linux is one) uses Path MTU discovery to try to determine the appropriate size to send over any arbitrary link. The way it works is very simple; in each direction, the hosts sends packets with the Don't Fragment bit set. When a packet which is too large reaches the router just before the link with the restricted MTU, since the don't fragment bit is set, the router drops the packet on the floor and sends back an ICMP Destination unreachable with a code which means "fragmentation needed and DF set", along with the maximum MTU of the constricting network link. This allows the sender to automatically determine maximum MTU for the hop, and the sender can then resend the TCP segment using a smaller packetsize, now that the maximum path MTU is known.

The problem with this comes with, as I mentioned earlier, bone-headed firewall maintainers who believe that all ICMP packets are bad and filters all of them. This includes the ICMP Destination unreacable packets which are needed to make path MTU function correctly. As a result, a site which is behind one of these firewalls will continually send big packets with the don't fragment bit set, which then get rejected when they hit the constricting link, but since the firewall filters out the ICMP "too big" message, the sending sight never knows that the packets are getting rejected, and so they can never send you anything.

This doesn't come up in normal operation for most hosts because most links support at least the ethernet maximum MTU of 1500, and if there is a constricting link, it is at the client endpoint (for example, the client is dialing up with PPP and so has a restricted MTU). At the client end point, it's not a problem, since the client knows that it's sending packets to an interface with a restricted MTU, and so it sends small packets. The problem comes when the constricting link is in the *middle* of the network path, and so Path MTU discovery is required in order to make things work. (Either that, or you have to learn to live with fragmentation with their attendant disadvantage).

So this will come up if you are using a PPP to connect to your gateway, and then you use NAT to allow machines on the local ethernet to gain access to the network via your singleton PPP connection. It also comes up with those folks using DSL where the providers are using the abomination also known as PPP over Ethernet (PPPOE).

There are a couple of solutions you can use to solve this problem. One is to ask nicely to the web site administrators that they fix their firewall. Unfortunately, this doesn't always work. I am told that Amazon's web programmers were told about this problem, and they acknowledged it *as* a problem, but said they weren't allowed to fix it. (Probably because the bone-headed firewall administrator in their case was clueless, and they didn't have the power to override him.)

The second approach, assuming that the constricting link is close to you (usually it's the second-to-last hop in most scenarios), you can simply set a per route max segment size (MSS) parameter, which will force TCP packets using that particular route to be no larger than the MSS size --- in both directions. Given that the problem is usually on the link to the outside internet, and that connections to other hosts within the subnet are OK, it's usually a matter of setting the mss option only on the default route:

route add default gw 216.176.176.160 mss 1400

The final approach, which apparently some of the DSL providers use, is that on the cable modem box or on the DSLAM in the telco's central office, they are actively messing with the outgoing packets, by looking for TCP packets with the SYN bit set (which indicates the beginning of a TCP stream), and change the max MSS option in the IP header to be smaller than max MTU caused by the PPP over Ethernet overhead. This is incredibly ugly, and violates the IP protocol's end-to-end argument. It also breaks in the presence of IPSEC, since the DSL provider won't be able to muck with the packet without breaking the cryptographic checksums.

So it's completely ugly. Still, I imagine that Rusty will no doubt be writing a new "packet fucking" module in ipchains to support this kind of TCP syn option rewriting. :-)

.... except if you want to build stand-alone kernel modules that work against the kernel that you are currently booting.

This still requires that /usr/include/linux and /usr/include/asm match the kernel you are currently building. Some packages will now use /usr/src/linux/include/{linux,asm} in preference if they exist, or allow the user to manually specify the location of the kernel source tree to use, but these conventions haven't been universally standardized yet.

Doing so would be a good idea, BTW. If we can all agree that "this is the way to do things in Linux 2.4", and make sure all of the distributions are informed of that fact, that would be Good Thing (tm). My personal nomination of the standard way to do things is to assume that /usr/src/linux is a symlink to kernel sources corresponding to the default kernel being booted on that machine, and that stand-alone device drivers that need to compile against a kernel should default to /usr/src/linux, but there should be an easy way for users to override that and specify some other kernel source tree if necessary. Any objections to such an approach?

I went looking for ipfwadm.o in net. Nope, it's in misc. What about af_packet.o? That's in misc too.

It makes some sort of sense: net/ seems to contain network *device* drivers. This now includes ppp (but it didn't before).

And why isn't there a sound directory? Etc.

If there must be directories, IMO "video" and "sound" should have priority over "ieee1394".