Friday, August 21, 2009

Someone wants to patent three-year-old public research

My public three-year-old research, that is (well, five-year-old in the mean time, but the patent was filed in 2007). A couple of guys apparently read a paper that I presented at the very nice 2004 Workshop on Dynamic Analysis (WODA), held in conjunction with the International Conference on Sofware Engineering.

The paper was about the precise detection of memory leaks. Rather than only telling you when a program exits that you did not free a particular block of memory, the paper described a way to also report where exactly you lost your last pointer to said block. This is quite useful in complex programs where memory allocation may happen in an initialisation function, and as a result only knowing where it has been allocated is not really helpful in figuring out how to solve the problem.

The basic technique was/is based on plain reference counting with a couple of extra tricks to make it work in an uncooperative environment. Dynamic binary instrumentation of the target program enabled us to intercept all memory management routines and all memory accesses. We then recorded the addresses of all allocated memory blocks tracked them as they are passed around in the program.

If I understand the description in Patentese of their patent application correctly, they state that they refined the technique so that it can now also deal with the situation where the pointers passed around do not point to the beginning, but somewhere in the middle of an allocated memory block. Of course, this description is largely irrelevant when it comes down to determining what they are actually claiming a monopoly on.

The claims of the patent are what define its legal scope, i.e., what the applicants want exclusive rights to. This application has only 11 claims, of which three are independent. Furthermore, these three independent claims are basically identical:
  1. method claim: the algorithm itself (claim 1)
  2. system and method claim: a computer running a program containing the algorithm (claim 6)
  3. product claim: a program containing the algorithm (claim 11)

The reason for having these three claim forms is purely for litigation purposes. The first are applicable when someone is using the algorithm (i.e., the users of the software), the final one in case someone distributes a program the contains the algorithm (i.e., the programmer)

Next, there are eight dependent claims. Four depend on claim 1, the other four on claim 6. Again, these two sets mirror each other.

I'm not going to dissect the independent claims in detail, but in short: they claim exactly what we described in that paper. They will probably contest that there is one difference, described by this word soup from their claim:
the modifying of the reference count being capable of including modification for a memory location that is not at the start of the given allocation of the heap allocated memory
While in their description they claim that we did not consider that situation, let me cite from the paper:
Another kind of false positive can occur since we only track references to the start of a memory block. In practice, we only experienced this in the case of C++ code, where in some cases constructors return a pointer to sizeof(void*) bytes past the start of the allocated block. We compensated for this by treating such pointers also as references to blocks. After this adaption, we did not encounter any further reported false positives due to pointers not pointing to the start of a block.
Obviously, the above could be extended to treat pointers anywhere into the block as a valid pointer to said block. One person's omission of spelling something out is another person's invention, obviously.

The dependent claims, which you have to read as refinements of the independent claims they refer to, simply describe the (very well known) concept of reference counting and how they apply to tracking memory leaks. This is all explicitly described in the paper.

If the patent is ever granted, I doubt that it will be enforceable, except maybe before a Texas court. I also doubt that they will actually try to enforce it. It's probably just intended to embellish someone's resume, or to help enlarge the "IP" bubble of some company's assets. You can bet that it has nothing to do with innovation though.


  1. This is ridicolous.
    By the way - what's the license of your test code?
    You should sue them if you have the time and resources for it.
    You could claim that their "inventive step" was too small, as they based too much of it on your code.

  2. @Natanael:

    My test code was GPL, but that doesn't really matter as far as the patent is concerned. These guys may even never have looked at the code, since the technique was completely described in the published paper (which did not contain any code).

    I don't think you can sue anyone over simply filing a patent application. Even that were possible, I wouldn't be interested in wasting my time and money on that. What may however be possible and worthwhile is to contact the reviewer at the US Patent Office and give him some comments.

    I agree that there is a distinct lack of "non-obviousness" (the US' equivalent of the European "inventive step"), but that goes for pretty much all software patents out there if you're somewhat familiar with the subject the patent is about. That seldom stops a patent from being granted though, because the legal definition of obviousness and the way a computer programmer or scientist would interpret that term is quite different.