Bug 83938 - CVE-2014-3638 follow-up: improve data structures for pending replies
Summary: CVE-2014-3638 follow-up: improve data structures for pending replies
Status: REOPENED
Alias: None
Product: dbus
Classification: Unclassified
Component: core (show other bugs)
Version: 1.5
Hardware: All All
: medium enhancement
Assignee: D-Bus Maintainers
QA Contact: D-Bus Maintainers
URL:
Whiteboard: review-, more discussion
Keywords: patch
Depends on: 81053
Blocks:
  Show dependency treegraph
 
Reported: 2014-09-16 16:39 UTC by Simon McVittie
Modified: 2014-09-25 14:43 UTC (History)
4 users (show)

See Also:
i915 platform:
i915 features:


Attachments
[PATCH v2] pending replies: use better data structures than a linked list (45.25 KB, patch)
2014-09-16 16:41 UTC, Simon McVittie
Details | Splinter Review

Note You need to log in before you can comment on or make changes to this bug.
Description Simon McVittie 2014-09-16 16:39:19 UTC
+++ This bug was initially created as a clone of Bug #81053 +++

Alban wrote: ----8<----

I have an issue with pending replies. It is related to the following limits:

- max_replies_per_connection; default: 1024*8; session=50000
- reply_timeout; default: -1 (disabled)
- max_connections_per_user=256
- max_replies total = max_replies_per_connection
                      * max_connections_per_user
                    = 256*1024*8 per user

So a single user on the system bus could generate up to 2097152 pending replies that dbus-daemon has to track. All pending replies are tracked in the linked list "connections->pending_replies", see bus_connections_check_reply().

So every time a benign connection sends a D-Bus method, dbus-daemon has to iterate over this linked list. It is taking too much time and during that time, it uses the cpu and does not process other D-Bus connections.

While a malicious process creates as many pending requests as it can, I tested how long a benign method takes with the following command:

  time dbus-send --system  --print-reply \
    --dest=org.freedesktop.DBus /org/freedesktop/DBus \
    org.freedesktop.DBus.GetConnectionUnixProcessID \
    string::1.76

After enough pending replies being added in the linked list, the simple dbus-send takes more than _DBUS_DEFAULT_TIMEOUT_VALUE (25 seconds) and it fails.

The "time" command gave me once the following result:
real	1m58.026s

The authentication steps are not included in the 25 seconds timeout, that's why "time" displays more than 25 seconds.

So while dbus-daemon is busy looping taking the cpu, D-Bus methods fail (depending on reply_timeout and applications' timeout) and authentication fails (depending on auth_timeout).

----8<----

The quick fix for this in 1.8.8 was to reduce the number of pending replies that are allowed, to the point where O(n) is not a big problem any more.

However, in 1.9 we should use better data structures.
Comment 1 Simon McVittie 2014-09-16 16:41:38 UTC
Created attachment 106384 [details] [review]
[PATCH v2] pending replies: use better data structures than a linked  list

From: Alban Crequy <alban.crequy@collabora.co.uk>

BusExpireList used to keep track of BusExpireItems/BusPendingReply in a unique
linked list without knowledge of the BusPendingReply struct. Iterating on the
linked list takes a linear time on the number of items. It is inefficient
because it iterates on items not relevant to the DBusConnection considered.

The total number of BusExpireItems on the bus can be quite large: with the
default limits on the system bus, it is 2097152 per user:
max_replies_per_connection * max_connections_per_user = (1024 * 8) * 256

The items in the BusExpireList are looked up in 3 different ways:
  1. When sending a D-Bus method call in bus_connections_expect_reply():
     check whether the exact triplet (DBusConnection caller, DBusConnection
     callee, dbus_uint32_t reply_serial) already exists and check whether the
     number of pending replies associated to the caller is over
     max_replies_per_connection.
  2. When sending a D-Bus return call in bus_connections_check_reply():
     find the exact triplet (DBusConnection caller, DBusConnection callee,
     dbus_uint32_t reply_serial)
  3. When a DBusConnection disconnects, iterate on the pending replies
     associated either with the connection as a caller or as a callee.

It becomes overly complicated to make a better data structure for theses use
cases without BusExpireItem having a reference to the caller, callee and
serial. BusExpireList was written in a generic way but is only used for pending
replies. This patch gets rid of the generic programming and store each
BusExpireItem in two hash tables keyed respectively by DBusConnection caller
and by DBusConnection callee.

In order to implement transactions correctly, a pending reply needs to be
removed and re-added in the BusExpireList without memory allocations. It was
done with linked lists by keeping the reference to the DBusList in
CheckPendingReplyData. In this new implementation, BusExpireItem has a new
field "dbus_bool_t deleted" and the BusExpireItem is only marked as deleted
when preparing the transaction and removed effectively when the transaction
finishes, with the bus_transaction_add_cancel_hook callbacks.

https://bugs.freedesktop.org/show_bug.cgi?id=81053
---
v1: first version
v2:
 - add some documentation
 - use the new API in the unit test
 - fix counting of deleted & non-deleted items
 - fix double free in bus_connections_check_reply
 - fix caller/callee confusion in bus_expire_list_foreach
 - fix memleaks in case of OOM in _bus_expire_list_add_helper
Comment 2 Simon McVittie 2014-09-16 18:54:53 UTC
Comment on attachment 106384 [details] [review]
[PATCH v2] pending replies: use better data structures than a linked  list

Review of attachment 106384 [details] [review]:
-----------------------------------------------------------------

::: bus/expirelist.c
@@ +31,4 @@
>  
>  struct BusExpireList
>  {
> +  /* hash:

The only things I can see that these data structures could do more efficiently than a single hash table are "drop all BusExpireItem records for this caller" and "drop all BusExpireItem records for this callee" (both when a connection disconnects), and you currently do that by O(n) iteration over the whole lot anyway...

If O(n) iteration on each disconnection is good enough, we could introduce a special DBusHash mode for BusExpireItem, or for "use caller-supplied hashing and equality functions" like GHashTable, to be able to treat BusExpireItem as a (caller, callee, serial) triple and have one map

    (caller, callee, serial) -> BusExpireItem

?

@@ +48,5 @@
> +   *          - value: hash:
> +   *                   - key: int reply_serial
> +   *                   - value: BusExpireItem *item
> +   */
> +  DBusHashTable *callee;

In particular, I'm not convinced you need this hash table at all?

@@ +71,5 @@
>  
>  static dbus_bool_t expire_timeout_handler (void *data);
>  
> +static void
> +_safe_hash_unref (DBusHashTable *table)

Deserves a pseudo-doc-comment, I think:

/* because DBusHash will call your_free_function(NULL)
 * even if NULL was never actually stored in the hash */

@@ +128,4 @@
>  void
>  bus_expire_list_free (BusExpireList *list)
>  {
> +  _dbus_assert (list->non_deleted_items_count == 0);

Should you assert that there are no deleted items either?

@@ +425,5 @@
>  }
>  
> +/**
> + * Mark the item for deletion next time do_expiration_with_monotonic_time() is
> + * called. The item's memory will also be released by dbus_free.

I think "... released by dbus_free at that time" would make it clearer that it isn't freed right now

@@ +519,5 @@
> +    }
> +
> +  found3 = _dbus_hash_iter_lookup (hash3,
> +              _DBUS_INT_TO_POINTER (item->reply_serial), FALSE, &iter3);
> +  _dbus_assert (!found3);

What guarantees that this assertion will not fail?

(It seems the answer is bus_connections_expect_reply(). That deserves a comment here, I think.)

@@ +674,5 @@
> +  DBusHashTable *hash;
> +  BusExpireItem *item;
> +
> +  hash = _dbus_hash_table_lookup_uintptr (list->caller,
> +                                          _DBUS_POINTER_TO_INT (caller));

All lookups in this hash should be (uintptr_t) caller.

Confusingly, _DBUS_POINTER_TO_INT returns an intptr_t, not an int. It's still, strictly speaking, the wrong type (even if in practice the compiler will do the right thing for implicit signed -> unsigned conversion).

@@ +679,5 @@
> +  if (!hash)
> +    return NULL;
> +
> +  hash = _dbus_hash_table_lookup_uintptr (hash,
> +                                          _DBUS_POINTER_TO_INT (callee));

Same

@@ +683,5 @@
> +                                          _DBUS_POINTER_TO_INT (callee));
> +  if (!hash)
> +    return NULL;
> +
> +  item = _dbus_hash_table_lookup_int (hash, reply_serial);

This innermost hash table should really be keyed by something whose range is a superset of dbus_uint32_t's, like uintptr.

@@ +805,5 @@
> +  _dbus_assert (list->deleted_items_count == 0);
> +  _dbus_assert (list->non_deleted_items_count == 0);
> +
> +  /* add plenty of items */
> +  for (i = 0; i < 6; i++)

i < TEST_CONN_COUNT, etc.

@@ +830,5 @@
> +              dbus_free (items[i][j][k]);
> +            }
> +        }
> +
> +  _dbus_assert (list->deleted_items_count == 6 * 6 * 6 / 3);

s/6/TEST_CONN_COUNT/

@@ +842,5 @@
> +  _dbus_verbose ("next_interval = %d\n", next_interval);
> +  _dbus_assert (next_interval == 1);
> +  _dbus_assert (list->deleted_items_count == 0);
> +  _dbus_assert (list->non_deleted_items_count == 6 * 6 * 6 / 3);
> +  for (i = 0; i < 6; i++)

and here
Comment 3 Simon McVittie 2014-09-16 18:58:57 UTC
So the big questions I have here are:

How large does max_connections_per_user * max_replies_per_connection have to be to make these nested hash tables more efficient than the O(n) list?

If you're going to leave bus_connection_drop_pending_replies() as a linear lookup, why did you use nested hash tables at all?

How large do the limits have to get before a non-linear bus_connection_drop_pending_replies() becomes worth it?
Comment 4 Simon McVittie 2014-09-16 19:10:07 UTC
(In reply to comment #1)
> The items in the BusExpireList are looked up in 3 different ways:
>   1. When sending a D-Bus method call in bus_connections_expect_reply():
>      check whether the exact triplet (DBusConnection caller, DBusConnection
>      callee, dbus_uint32_t reply_serial) already exists and check whether the
>      number of pending replies associated to the caller is over
>      max_replies_per_connection.

The biggest cost an attacker can incur per second is currently O(max connections per user * max replies per connection * method calls / sec).

If the nested hash tables perform perfectly (optimistic assumption), your changes reduce this to O(method calls / sec).

A flat hash table keyed by triples would also be O(method calls / sec).

>   2. When sending a D-Bus return call in bus_connections_check_reply():
>      find the exact triplet (DBusConnection caller, DBusConnection callee,
>      dbus_uint32_t reply_serial)

The same.

>   3. When a DBusConnection disconnects, iterate on the pending replies
>      associated either with the connection as a caller or as a callee.

This is currently O(max connections per user * max replies per connection * reconnect cycles per second).

Your changes do not alter this. A flat hash table keyed by triples would also not alter this.

With a perfect implementation (making better use of the nested hash tables), optimistically assuming hash tables are O(1), this would reduce to O(reconnect cycles per second).

I suspect that the flat hash table has a bigger constant multiplier than the linked list, and your nested hash tables are likely to have a bigger constant multiplier than that, from the increased malloc/free activity if nothing else.
Comment 5 Simon McVittie 2014-09-16 19:14:55 UTC
(In reply to comment #4)
> >   3. When a DBusConnection disconnects, iterate on the pending replies
> >      associated either with the connection as a caller or as a callee.
> 
> This is currently O(max connections per user * max replies per connection *
> reconnect cycles per second).

An attacker trying to waste CPU time like this would be limited by the fact that we've fixed Bug #80919, I think?
Comment 6 Alban Crequy 2014-09-18 16:23:16 UTC
(In reply to comment #3)
> If you're going to leave bus_connection_drop_pending_replies() as a linear
> lookup, why did you use nested hash tables at all?

bus_connection_drop_pending_replies() itself is not linear on the total amount of BusExpireItem but only linear on the amount of BusExpireItem it needs to handle. so it is the best we can do. See bus_expire_list_foreach(): the first level of nested hash table is not an iterator loop but a simple lookup. For this to work, I make use of both top-level hash tables "caller" and "callee".

However, the callbacks use bus_expire_list_recheck_immediately() so it will trigger do_expiration_with_monotonic_time()/_bus_expire_list_cleanup_helper() to be run at the next iteration of the main loop, and the cleanup is linear on the total amount of BusExpireItem.

Since DBusHashTable does not have an API to insert an element without allocating memory (only DBusList has such API), I used the "dbus_bool_t deleted" trick to be able to complete or rollback a deletion. I have not found any way to implement do_expiration_with_monotonic_time()/_bus_expire_list_cleanup_helper() in a non-linear way because of the need to be able to rollback transactions. Ideas welcome here.


Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.