[Date Prev][Date Next]
Distributed ppolicy state
- To: OpenLDAPemail@example.com
- Subject: Distributed ppolicy state
- From: Howard Chu <firstname.lastname@example.org>
- Date: Thu, 22 Oct 2009 00:44:36 -0700
- User-agent: Mozilla/5.0 (X11; U; Linux i686; rv:184.108.40.206pre) Gecko/20091012 SeaMonkey/2.0a1pre Firefox/3.0.3
One of the major concerns I still have with password policy is the issue of
the overhead involved in maintaining so many policy state variables for
authentication failure / lockout tracking. It turns what would otherwise be
pure read operations into writes, which is already troublesome for some cases.
But in the context of replication, the problem can be multiplied by the number
of replicas in use. Avoiding this write magnification effect is one of the
reasons the initial versions of the ppolicy overlay explicitly prevented its
state updates from being replicated. Replicating these state updates for every
authentication request simply won't scale.
Unfortunately the braindead account lockout policy really doesn't work well
without this sort of state information.
The problem is not much different from the scaling issues we have to deal with
in making code run well on multiprocessor / multicore machines. Having
developed effective solutions to those problems, we ought to be able to apply
the same thinking to this as well.
The key to excellent scaling is the so-called "shared-nothing" approach, where
every processor just uses its own local resources and never has to synchronize
with ( == wait for) any other processor, but for the most part it's a design
ideal, not something you can do perfectly in practice. However, we have some
recent examples in the slapd code where we've been able to use this approach
to good effect.
In the connection manager, we used to handle monitoring/counter information
(number of ops, type of ops, etc) in a single counter, which required a lot of
locking overhead to update. We now use an array of counters per thread, and
each thread can update its own counters for free, completely eliminating the
locking overhead. The trick is in recognizing that this type of info is
written far more often than it is read, so optimizing the update case is far
more important than optimizing the query case. When someone tries to read the
counters that are exposed in back-monitor, then we simply iterate across the
arrays and tally up the counters then. Since there's no particular requirement
that all the counters be read in the same instant in time, all of these
reads/updates can be performed without locking, so again we get it for free,
no synchronization overhead at all.
So, it should now be obvious where we should go with the replication issue...
Ideally, you want password policy enforcement rules that don't even need
global state at all. IMO, the best approach is still to keep policy state
private to each DSA, and this still makes sense for DSAs that are
topologically remote. E.g., assume you have a pair of servers, each in two
separate cities. It's unlikely that a login attempt on one server will be in
any way connected to a simultaneous login attempt on the other server. And in
the face of bot attack, the rate of logins will probably be high enough to
swamp the channel between the two servers, resulting in queueing delays that
ultimately aggregate several of the updates on the attacked server into just a
single update on the remote server. (E.g., N separate failure updates on one
server will coalesce into a single update on the remote server.)
Therefore, most of the time it's pointless for each server to try to
immediately update the other with login failure info.
In the case of a local, load-balanced cluster of replicas, where the network
latency between DSAs is very low, the natural coalescing of updates may not
occur as often. Still, it would be better if the updates didn't happen at all.
And in such an environment, where the DSAs are so close together that latency
is low, distributing reads is still cheaper than distributing writes. So, the
correct way to implement this global state is to keep it distributed
separately during writes, and collect it during reads.
I'm looking for a way to express this in the schema and in the ppolicy draft,
but I'm not sure how just yet. It strikes me that X.500 probably already has a
type of distributed/collective attribute but I haven't looked yet.
Also I think we can take this a step further, but haven't thought it through
all the way yet. If you typically have login failures coming from a single
client, it should be sufficient to always route that client's requests to the
same DSA, and have all of its failure tracking done locally/privately on that DSA.
At the other end, if you have an attack mounted by a number of separate
machines, it's not clear that you must necessarily collect the state from
every DSA on every authentication request. E.g., if you're setting a lockout
based on the number of login failures, once the failure counter on a single
DSA reaches the lockout threshold, it doesn't matter any more what the failure
counter is on any other DSA, so that DSA no longer needs to look for the
values on any other node.
If a client comes along and does a search to retrieve the policy state, e.g.
looking for the last successful login or the last failure, then you want
whatever DSA receives the request to broadcast the search to all the other
DSAs and collate the results for the client by default. (Note that simple
aggregation only works for multivalued attributes; for single-valued
attributes like pwdLastSuccess you have to know to pick the most recent
value.) And probably you should be able to specify a control (like
ManageDSAit) to disable this automatic broadcast and only retrieve the value
from a single DSA.
I realize that the points listed above about login attacks miss several attack
scenarios. I think more of the scenarios need to be outlined and analyzed
before moving forward with any recommendations on lockout behavior; the
internet today is pretty different from when these lockout mechanisms were
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/