By Jonathan Corbet
April 25, 2011
For many years we have heard warnings that software patents pose a threat
to the free software community. Repeated warnings have a tendency to fade
into the noise if they are not followed by real problems; to many, the
patent threat may have seemed like one of those problems we often hear
about but never experience. The recent ruling in the US that Google is
guilty of infringing a software patent held by a patent troll named
"Bedrock Computer Technologies" serves as a reminder that the threat is
real, and that solutions will not be easy to come by.
The patent in question is #5,893,120
- "Methods and apparatus for information storage and retrieval using a
hashing technique with external chaining and on-the-fly removal of expired
data." The independent claims from the patent are short and simple; #3
reads like this:
A method for storing and retrieving information records using a
linked list to store and provide access to the records, at least
some of the records automatically expiring, the method comprising
the steps of:
- accessing the linked list of records,
- identifying at least some of the automatically expired ones of the records, and
- removing at least some of the automatically expired records from
the linked list when the linked list is accessed.
Needless to say, numerous people who are "skilled in the art" have
concluded that there is little that is original or non-obvious in this
claim. In its defense, Google argued that the technique is, indeed,
obvious (to the point that it should be invalidated under the Bilski
ruling), that the patent is invalid due to prior art, and that Linux did
not infringe upon the patent in any case. All of those arguments were
pushed aside by the jury, which found Google guilty and granted an award of
$5 million, a small fraction of the $183 million requested by Bedrock.
The
full set of docket entries - almost 800 of them - are listed on the
net. Many of the interesting ones are sealed, though, and unavailable to
the public. We are all affected by this ruling, but we are unable to read
most of testimony that led up to it. Instead, the bulk
of the publicly-available information has to do with the various bits of
legal jousting which set timetables and which control the evidence that can
be presented. Thus, for example, we learn that a late attempt to bring in
Alan Cox to testify on his early routing table work was pushed back and
eventually abandoned. Still, there are some interesting things to be
learned by plowing through these documents.
The code
The code in question is that which maintains the networking stack's routing
cache - some of the oldest code in the kernel; it can be found in
.../net/ipv4/route.c. This code maintains a hash table of linked
lists containing routing entries; as the world changes, entries must be
added or deleted. Bedrock claims that its patent is infringed by this
code, though even Bedrock has, more or less, admitted
[PDF] that any infringement
will have been done inadvertently, with no knowledge that the patent
existed. The various defendants (Google is only one of the companies
targeted) have made various arguments, starting with the claim that the
code does not use the algorithm described in the patent at all; see this
brief [PDF] for a summary of that argument:
The accused instrumentalities - servers using versions of the Linux
kernel prior to 2.6.25 - do not meet all elements of the '120 patent
because: (1) removal of records does not occur "when the linked
list is accessed" ('120 patent claims 1, 3, 4, 5, 7, and 8); (2)
the removed records are not "expired" ('120 patent claims 1, 3, 5,
and 7); (3) there is no "dynamically determining maximum number" of
expired records to remove ('120 patent claims 2, 4, 6, and 8) (for
all accused versions); (4) the accused code does not remove an
expired record while using the record search means to search for a
record to delete (for all accused versions); and (5) there is no
evidence that the accused code has ever executed, as required by
all asserted claims.
What one learns early on is that how terms like "when the linked list is
accessed" are defined is crucial in a decision regarding infringement. That
is where the "claim construction" process comes into play; for the full,
gory details of how it was done in this case, see docket
#369 [PDF]. There was a big fight, for example, over whether "removing
from the linked list" required deallocation of the entry that was removed;
Bedrock won that one and got a ruling that deallocation is a separate
operation. The biggest fight seemed to be over whether removal "when the
linked list is accessed" meant that the structure needed to be removed
during the traversal of the list; Bedrock seemed to think that removal at
some later time qualified, but the court disagreed. That should have been
a decisive victory for the defense, but it appears to not have been enough.
Invalidation attempts
There was also a determined effort to have the patent ruled invalid due to
prior art. It is interesting to note that, in early 2010, a separate
challenge to this patent was raised at the US Patent and Trade Office,
citing four other patents as prior art; the patent was, in fact,
invalidated by the PTO last July. But Bedrock was then allowed to tweak
the wording of the claims until the PTO agreed that the modified patent
was, once again, valid. This history shows why attempts to kill patents so
rarely achieve the desired results: patents can never truly be killed this
way. Instead, the owner is allowed to make changes, resulting in zombie
patents that return from the dead to terrorize again and again. A second challenge
to the patent was filed in January of this year; it cites two more patents
as prior art; a ruling has not yet been made in this case.
The defendants' attempt to invalidate the patent does not depend on that
prior art at all, interestingly; instead, this
challenge [PDF] is based on the Linux code itself. They claim that the
code in route.c has not changed materially since the 1.3.x days
and that, in particular, the 2.0.1 version was quite close to what we have
now. These prior versions, it is claimed, include all of the claims of
Bedrock's patents, and thus serve as prior art invalidating the patent.
One might find some amusing irony in the claim that older code implemented
the patented technique while current code - said to be about the same -
does not. The point is, of course, that if the current code is said to
infringe, the older code should be said to implement the patent in the same
way. Either both versions implement the patented algorithm (in which case
it's invalid due to prior art) or neither does.
The argument seems strong enough. We cannot know how Bedrock argued
against this reasoning, though - its response is sealed and inaccessible.
It is also worth noting that the US PTO has not considered older Linux
releases as prior art when reevaluating this patent; it would appear that
the challengers have not asked it to.
In the midst of all this, Red Hat has filed a suit of its own against
Bedrock. It seems that some Red Hat customers have been getting nervous
about Bedrock's activity and asked for help; Red Hat responded by filing a
preemptive suit asking that the patent be ruled invalid and that Red Hat's
products be deemed to be non-infringing. That case is still in the works;
Red Hat also tried
to jump into the Google et al. case [PDF], but that attempt was denied by the judge.
In reading the filings, one also learns the Match.com (another defendant in
the suit) made a deal with Bedrock and was allowed to drop out.
Now what?
This verdict has been widely publicized as a big defeat for Linux. Perhaps
it is, but not for the reasons being cited - this particular patent is not
a huge problem, but the fact that patent trolls can win judgments against
Linux is problematic indeed. If need be, the kernel's
routing table code can be tweaked to avoid infringing Bedrock's patent;
indeed, Docket
#445 [PDF] lets slip the fact that Google has already changed its
kernels to that effect. There could be a case for past infringement, but
there need be no real fear that Bedrock will be out there collecting rents
from Linux users in the future, even if the ruling stands.
We can hope that the ruling will, in fact, not stand. If Red Hat prevails
in its separate case, the verdict against Google will have to be
reevaluated. Even in the absence of a victory there, Google's defense was
strong enough to warrant an appeal. Google is just one of a number of
companies which cannot let it be thought that Linux is an easy target for
shakedowns by patent trolls; there is a strong incentive for the company to
keep on fighting, even if that fight is likely to cost more than the
(relatively small) $5 million it has been told to pay Bedrock. For
all of our sake, we must hope that all of the companies involved in this
case find it worth their while to get the ruling reversed.
If Bedrock loses in the end, other potential trolls will hopefully be
deterred from jumping in with suits of their own. But there can be no
doubt that more of these cases will come along; that is really just the
nature of the software patent system. Until we can get some sort of
high-level reform, we will always have to fear trolls wielding patents on
elementary techniques.
(
Log in to post comments)