Some recent work has addressed denial of service issues in the design of IPC (Inter process communication) primitives. We considered these issues somewhat belatedly in Keykos under the rubric “promptness”. Here are some thoughts on the broader problem.

There is some program we will call the server here that is trusted by all the parties in sight to be prompt. This means that it will take the available precautions to reply to messages without delay, even to hostile questions, so as to be available for polite questions. The Keykos meter construct was designed so that a simple user mode scheduler could insure progress of a behaving application (BA) in the presence of a misbehaving application (MA). Now what if both BA and MA are both authorized to send queries to the sever, however? Is MA in a position to bolix the server so that it cannot serve BA?

There are several ways MA can impact the service and while the server has some responsibility in this regard, there are some features of the foundation that are necessary for the server to provide prompt service.

Threats to Service

MA can ask the server an infeasible question.
  1. The server may be designed and coded to detect such questions and promptly reject all of the infeasible requests. In some cases this will requires rejecting too many as there are many problems with no such decision procedure.
  2. The server can demand a meter from the requester and run the query on the requester’s nickel. This solution has too much overhead for some applications. It is also unavailable at lower levels; the factory cannot use this as it is itself a tool of deploying MA’s meter.
MA spams the server incessantly asking questions, spending only a few instructions (and a minuscule part of his meter ration) re-asking the same question. The server must probably spend 100 times as much meter resources responding (by rejection) to this spam as the spammer.
Even if the server adopts technique 2 above it will spend many times its resources replying to the question as it took to ask it.
One technique is for the server’s domain to be marked (with a yet unimplemented mark) indicating to the kernel that the invoker’s meter must be docked by some amount each time the server accepts a message from a start key. The amount might be standard and equivalent to several gate jumps for the purpose of solving this problem.
Another problem arises regarding returning a response to MA. What if the string in the response is to be deposited in MA’s space at an address that is not valid at the time of the response.
Keykos currently discards the string with the attitude that the query was ill posed, for MA could have avoided this. This is tenable in Keykos where strings are now limited to 4KB. But this is not a practical defense when there is a large peak to average ratio in the length of the reply. It is poor economy to always require the space necessary for the largest possible response. When circumstances allow solution number 2 above, MA’s user mode fault handler can respond at its leisure without impacting the server’s service.