KSM runs into patent trouble
Please consider subscribing to LWN Subscriptions are the lifeblood of LWN.net. If you appreciate this content and would like to see more of it, your subscription will help to ensure that LWN continues to thrive. Please visit this page to join up and keep LWN on the net. |
On the kernel page a few weeks ago, we took a look at KSM, a technique to reduce memory usage by sharing identical pages. Currently proposed for inclusion in the mainline kernel, KSM implements a potentially useful—but not particularly new—mechanism. Unfortunately, before it can be examined on its technical merits, it may run afoul of what is essentially a political problem: software patents.
The basic idea behind KSM is to find memory pages that have the same contents, then arrange for one copy to be shared amongst the various users. The kernel does some of this already for things like shared libraries, but there are numerous ways for identical pages to get created that the kernel does not know about directly, thus cannot coalesce. Examples include initialized memory (at startup or in caches) from multiple copies of the same program and virtualized guests that are running the same operating system and application programs.
Unfortunately, as Dmitri Monakhov points out, the KSM technique appears to be patented by VMware. A patent for "Content-based, transparent sharing of memory units" was filed in July 2001 and granted in September 2004. The abstract seems to clearly cover the ideas behind KSM:
It should be noted that the abstract has no legal bearing, that comes from the—always tortuously worded—claims, which can be seen at the link above. In this case, as far as can be determined, the claims and abstract are in close agreement.
The dates above are rather important because there is some "prior art" to consider, namely the mergemem patch first announced in March of 1998. It is substantially the same as the patented idea: it looks for identical "context pages", then changes the memory mappings to point to a single copy-on-write page. This would seem to be a clear example of the idea being implemented well before the patent was filed, so it should invalidate the patent. As with everything surrounding software patents, though, it isn't as easy as that.
In order to invalidate a patent, either a court must rule that way or the
patent office must be convinced to re-examine it, then find that the prior
art makes it invalid. Both of these methods
take time and usually money and lawyers as well. Free software projects
may have time, but the other two are typically out of reach. Alan Cox suggests that "perhaps the
Linux Foundation and
some of the patent busters could take a look at mergemem and
re-examination
". While that might eventually resolve the problem,
it is a multi-year process at best.
The folks behind the KSM project are some of the kvm hackers from Qumranet—which is now part of Red Hat. It is certainly conceivable that VMware might consider kvm a competitor and try to use this patent as a "competitive" weapon. That concern is probably enough to keep KSM out of the mainline until the issue is resolved.
There is a much quicker resolution available should VMware wish to do so. Like IBM has done with the RCU patent, VMware could license its patent for use in GPL-licensed code. There is much to be gained by doing that, at least in terms of positive community relations, and there is little to be lost—unless VMware truly believes that the patent will stand up to scrutiny. Both VMware and its parent, EMC, are members of the Linux Foundation, so one could see a role for the foundation in helping to put that kind of agreement together.
The original mergemem idea did not make into the kernel, but the code is still available for those running Linux 2.2.9. It appears that it was not pushed very hard in the face of some security concerns—which will need to be addressed by KSM as well. Processes could create a page of memory with known contents then, after waiting for the checker process (or kernel thread) to run, see if memory usage has increased. Based on that information, one can determine if other processes have a page with identical values. It would seem rather difficult to exploit, but clearly does allow some information to leak.
It will come as no surprise to most LWN readers that software patents are an increasingly dense minefield that can derail free software projects. Unfortunately, it is the kind of problem that has no solution in the technical domain where such projects excel. The political arena is where any solution will have to come from, though there seems to be some hope that judicial opinions (like the Bilski decision) may limit the scope of the damage. It is a problem that we are likely to see more frequently until there is some kind of resolution.
(Log in to post comments)
KSM runs into patent trouble
Posted Dec 3, 2008 17:13 UTC (Wed) by flewellyn (subscriber, #5047) [Link]
Good gamesmanship, too
Posted Dec 3, 2008 19:05 UTC (Wed) by dmarti (subscriber, #11625) [Link]
If they license for GPL implementation right away, it sidelines some important stakeholders who would otherwise have an incentive for patent-busting. Then they're free to use the patent as a bargaining chip for cross-licensing with proprietary vendors, or as a revenue tool.Don't cut packing tape with your good kitchen knife if you want to keep it good.
Good gamesmanship, too
Posted Dec 3, 2008 19:38 UTC (Wed) by flewellyn (subscriber, #5047) [Link]
Kill software patents
Posted Dec 3, 2008 19:54 UTC (Wed) by dwheeler (guest, #1216) [Link]
We need patent reform, in particular, we need to eliminate software patents. Here's a URL with pointers to more information on eliminating software patents: http://www.dwheeler.com/essays/software-patents.html.
Kill software patents
Posted Dec 3, 2008 19:55 UTC (Wed) by flewellyn (subscriber, #5047) [Link]
Kill software patents
Posted Dec 4, 2008 16:15 UTC (Thu) by felixfix (subscriber, #242) [Link]
What we really need is an emphasis on originality, not a ban on one particular type of patents.
Kill software patents
Posted Dec 4, 2008 17:31 UTC (Thu) by lysse (guest, #3190) [Link]
Whilst obviousness is an additional problem, it's not the whole problem. Software patents do whole swathes of damage because software is the transliteration of mathematical algorithms. It's the difference between patenting a particular machine that multiplies by the operation of a series of switches and patenting the concept of multiplication itself.Consider the motivation for introducing patents. The argument usually put is that patents protect the inventor of a machine, who might have invested considerable sums in the development of that machine, from being unable to recoup his costs because someone else has duplicated that machine exactly and can now sell it for only the costs of manufacture, without the need to recoup development costs. Well - the costs of manufacture in the case of software are precisely zero, but so are the costs of development; someone else who develops a broadly functionally similar program is still likely to end up spending just as much (or as little) writing it as the original developer, even if they end up slavishly duplicating every single technique and algorithm of the original. (Moreover, that duplication becomes necessary in cases like file format compatibility, as we've seen... extensively.) In any case, the duplication of software is already adequately protected by copyright law - which, of course, does not extend to mechanisms, which is why patents were seen as required in the first place; copyright law only covers form, not function - but software is form; the function is provided by the machine on which the software runs.
Kill software patents
Posted Dec 4, 2008 17:56 UTC (Thu) by dlang (guest, #313) [Link]
it's also a very uneven playing field for a well established software company (with extensive distribution, advertising, and name recognition in place) compared to a startup.
as such it's still pretty easy for a large software company to reverse engineer and duplicate the functionality of a small companies product and then wipe out the small company (look what microsoft has done several times)
unlike other industries 'trade secrets' don't work in software because you have to distribute the exact instructions. you can obfuscate things to make it hard to figure out, but a determined person can just look at the instructions that you give to the CPU and see what you are doing.
in physical devices trade secrets can sometimes work because the secret can be in how the device was made.
now I am not arguing that software patents are a good thing, I'm just saying that you arguments for why they aren't are invalid.
Kill software patents
Posted Dec 14, 2008 2:01 UTC (Sun) by lysse (guest, #3190) [Link]
Still, well done; that strawman never saw it coming.
Prose analogy patents
Posted Dec 4, 2008 18:59 UTC (Thu) by dmarti (subscriber, #11625) [Link]
I haven't seen an argument in favor of software patents that doesn't also apply to prose analogy patents. For example, should Steve Oualline's thorough mailbox analogy to explain pointers in Practical C Programming be patentable? If it helps people get pointers and start programming in C sooner, it has immense value--but another author could reimplement it in different words and using newly-drawn pictures without licensing it from the patent department at O'Reilly and Associates. The lack of a patent here means that Steve lacks an incentive to create more prose analogies of value.
Prose analogy patents
Posted Dec 4, 2008 23:23 UTC (Thu) by tialaramex (subscriber, #21167) [Link]
Who says Steve lacks an incentive? It takes a profoundly narrow mind to look out into the world and conclude that (to pick some famous names from the shelves near me somewhat at random) Lewis Carroll, Ambrose Bierce and William Goldman were coldly calculating individuals, writing whatever would generate the maximum income. No, each of them had his reasons for writing, whether a pittance or a fortune was the reward, and in no case is their best work that which an accountant or a lawyer would have said was most certain to be profitable.
When we look historically, we find that the incentive granted by these new monopolies was always an incentive to people who were already rich, to screw people and get richer. The reality of software patents is patent trolls, just as the reality of US prohibition was organised crime and massive corruption in the police and judiciary. When you find yourself making a law to "fix" a problem that didn't exist and the law causes you problems you never had before, it's a bad law and ought to be repealed. And if the courts or the patent officials make bad law by practice where there was no law by statute, drive it out with better laws.
Prose analogy patents
Posted Dec 4, 2008 23:43 UTC (Thu) by felixfix (subscriber, #242) [Link]
I know it would eliminate the GPL, but I also believe that the GPL is only necessary in a world of copyright lawyers. The core idea behind GPL is that it is in everyone best interests to share work, such as the linux kernel, rather than hoard your own copy and struggle to keep up to date with continual merges to keep up with public changes. I have done that too often to think it a viable development method.
Thank you for reminding me again how much I detest the very idea of copyright.
Prose analogy patents
Posted Dec 5, 2008 1:20 UTC (Fri) by bojan (subscriber, #14302) [Link]
This really is a political problem. A powerful and influential minority convinced governments around the world that keeping their monopolies is a good idea. Well, if people are complaining when the price of petrol goes up, so should they when the price of music, books, films and software does the same. Otherwise, we've go nobody to blame but ourselves.
Prose analogy patents
Posted Dec 5, 2008 1:43 UTC (Fri) by felixfix (subscriber, #242) [Link]
Kill software patents
Posted Dec 5, 2008 0:38 UTC (Fri) by bojan (subscriber, #14302) [Link]
http://www.ipaustralia.gov.au/strategies/case_kambrk.shtml
Quite obviously:
- the inventor invented without patent protection
- many competitors entered the market, making the product cheap
- the inventor's company is still alive and well
I swear, if I didn't know better, I'd say that it was written by a disgruntled employee. There are overtones of sarcasm too - it completely reverts the logic as to why the patents are supposed to be a good idea (i.e. they tout "maximum profits for the inventor" rather than "public good"). It ends with "the inventor discovered our legally sanctined monopolies and is a happy monopolist these days". Hilarious!
Kill software patents
Posted Dec 5, 2008 23:49 UTC (Fri) by bignose (subscriber, #40) [Link]
I find all too little indication they have any awareness of a motivation for getting good ideas into the public domain. Instead, the *entire site* appears to buy into the idea that artificial, legally-enforced restriction of natural usage of information is a good thing because it's a motive for the gatekeepers to profit.
Kill software patents
Posted Dec 7, 2008 1:01 UTC (Sun) by bojan (subscriber, #14302) [Link]
Wouldn't Common Subexpression Elimination be considered prior art?
Posted Dec 3, 2008 18:03 UTC (Wed) by shapr (subscriber, #9077) [Link]
Wouldn't Common Subexpression Elimination be considered prior art?
Posted Dec 3, 2008 19:03 UTC (Wed) by flewellyn (subscriber, #5047) [Link]
KSM runs into patent trouble
Posted Dec 3, 2008 20:05 UTC (Wed) by jordanb (guest, #45668) [Link]
Without the publicity he's created this may never have become an issue. Certainly if you wanted to render just about any software unusable you could do so by researching all the potential patent conflicts and bring them to the attention of the programmers, forcing them to neuter their software to avoid "willful infringement."
As far as I'm concerned VMWare is the biggest pile of scumballs this side of NVIDIA so I have no doubt that they'll use this to maximize their own benefit. The biggest issue here (beyond the fact that the patent system is broken) is that well intentioned people should *not* be researching and advertising potential patent conflicts. Let the patent holders do their own homework, for Christ's sake!
KSM runs into patent trouble
Posted Dec 3, 2008 22:57 UTC (Wed) by tialaramex (subscriber, #21167) [Link]
KSM runs into patent trouble
Posted Dec 3, 2008 23:02 UTC (Wed) by mlankhorst (subscriber, #52260) [Link]
they said was: Don't look at patents. If you however still believe that
you infringe on one, only contact a lawyer, because the client attorney
conversations are confidential. Looking for software patents is just
asking for troubles. It's better to stay completely ignorant.
To the best of my knowledge, my current debian system infringes on zero
patents. :) .. and I'm not even going to look for anything that might
possibly infringe ..
KSM runs into patent trouble
Posted Dec 3, 2008 23:22 UTC (Wed) by drag (guest, #31333) [Link]
Willful violation of patents, if proven, triples the damages awarded to the patent holder. It's much better to ignore patents and accidentally violate them then be a position were the judge can be convinced that you probably knew about the patent.
KSM runs into patent trouble
Posted Dec 4, 2008 0:46 UTC (Thu) by kev009 (guest, #43906) [Link]
KSM runs into patent trouble
Posted Dec 4, 2008 4:26 UTC (Thu) by drag (guest, #31333) [Link]
It would require having a team of people who are experts in patent law and programming following all your developers around and checking on projects your using in order to try to link against patents.
Even then your not going to avoid lawsuits from patent trolls.
Since there is no practical defense against patents then there isn't much you can do. Sure if your notified, like in this case, then you are forced to act, but it's definitely not something you want to volunteer for, especially when your in business. No benefit for you, all pain, no profits.
Patents and LWN
Posted Dec 4, 2008 0:47 UTC (Thu) by dmarti (subscriber, #11625) [Link]
Attention corporate development managers! Now you can subscribe to the special no-patent-stories edition of LWN, only $1000 per seat!
Patents and LWN
Posted Dec 4, 2008 2:16 UTC (Thu) by corbet (editor, #1) [Link]
Hey, man, didn't you see the embargo date on the press release? We weren't going to announce that until next week!
Patents and LWN
Posted Dec 4, 2008 16:17 UTC (Thu) by felixfix (subscriber, #242) [Link]
KSM runs into patent trouble
Posted Dec 4, 2008 0:59 UTC (Thu) by kbee (subscriber, #4468) [Link]
What security issue?
Posted Dec 4, 2008 1:45 UTC (Thu) by NCunningham (subscriber, #6457) [Link]
> waiting for the checker process (or kernel thread) to run, see if memory
> usage has increased.
I don't believe that's a real security issue at all. Absolutely anything could run in the meantime, with memory being both freed and allocated by completely unrelated causes. At best, such processes would be able to say it was possible that the page was shared, which really says nothing.
What security issue?
Posted Dec 4, 2008 3:12 UTC (Thu) by mjg59 (subscriber, #23239) [Link]
Anything could run, but it's possible that nothing will. And that means that a sufficient number of repetitions may show a significant deviation from what you'd expect from chance alone, which is an information leak.
What security issue?
Posted Dec 5, 2008 0:11 UTC (Fri) by nix (subscriber, #2304) [Link]
there are far too many potential avenues, and when you get right down to
it they *are* one single system, so one process consuming a shareable
resource will always be observable by another process attempting to get
access to the same resource. (Crude example: time. Busywait, watching the
time: if it skips, you know someone else is using the same core.)
If you want to avoid information leaks, run the high-sensitivity no-leak
stuff on a different physical machine. Nothing else is safe enough for the
paranoid, and only the paranoid will really care about this anyway.
What security issue?
Posted Dec 11, 2008 14:49 UTC (Thu) by anton (subscriber, #25547) [Link]
I think a more reliable leak is to then write in the page, and see if the write takes a long time (due to copy-on-write). There were other potential information leaks discussed, but IMO they were all pretty far-fetched and can be defended against (e.g., don't make it predictable when pages will be merged; on the application side, when inputting passwords, initialize the buffer with random data).
KSM runs into patent trouble
Posted Dec 4, 2008 8:10 UTC (Thu) by Felix.Braun (guest, #3032) [Link]
KSM runs into patent trouble
Posted Dec 4, 2008 8:13 UTC (Thu) by Felix.Braun (guest, #3032) [Link]
KSM runs into patent trouble
Posted Dec 4, 2008 22:51 UTC (Thu) by adegeus (guest, #22055) [Link]
patent style has not worked out quite as succesful for
the IP lords so far.
Perhaps dragging this issue for another few years in the EU
is just enough before the whole patent system will collapse all
together. Remember that by 2013 there will be a stock
of 1 million stupid patent applications be waiting for
analysis by the USPTO, and the patent database will be
a black hole infringing itself from one side to the other.
Patents don't warrant a fork
Posted Dec 4, 2008 8:45 UTC (Thu) by khim (subscriber, #9252) [Link]
Other projects had such issues for years. GIF patend, IDEA (ecryption algorythm) patent, etc. They all just had switches to enable them (default is "disabled", of course). Remember: kernel source can not infringe the patent - it's just a bunch of text. If you want to create binary - it's up to you to prove taht you are not infringing. The one who'll bring compiled binary of KSM to US will be infringer, not kernel developers...
Patents don't warrant a fork
Posted Dec 5, 2008 13:21 UTC (Fri) by cortana (subscriber, #24596) [Link]
KSM runs into patent trouble
Posted Dec 4, 2008 8:17 UTC (Thu) by hltbdivl (guest, #39740) [Link]
KSM runs into patent trouble
Posted Dec 4, 2008 14:52 UTC (Thu) by jake (editor, #205) [Link]
> The upper-case 'W' name was replaced quite a few years back, I believe.
Ahhh, so it is. Fixed, thanks!
jake
KSM runs into patent trouble
Posted Dec 4, 2008 10:54 UTC (Thu) by berndp (guest, #52035) [Link]
KSM runs into patent trouble
Posted Dec 4, 2008 11:39 UTC (Thu) by etienne_lorrain@yahoo.fr (guest, #38022) [Link]
To at least have the same protection as non open-source software...
KSM runs into patent trouble
Posted Dec 11, 2008 18:10 UTC (Thu) by xorbe (guest, #3165) [Link]