netdev - Re: inetpeer with create==0

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 3 Mar 2011 14:27:40 +0800
From:	Changli Gao <xiaosuo@...il.com>
To:	David Miller <davem@...emloft.net>
Cc:	eric.dumazet@...il.com, netdev@...r.kernel.org
Subject: Re: inetpeer with create==0

On Thu, Mar 3, 2011 at 1:36 PM, David Miller <davem@...emloft.net> wrote:
>
> Because trie eliminates all of the issues of having to size a hash
> table, dynamically resize it, etc.
>
> Trie gives well bounded performance dependent solely upon size of
> the table, rather than access patterns, distribution of keys, and
> how perfect hash function is.

Thanks for your explaination. Routing cache has all of these issues. :)

>
> We used to use a hash table for the page cache too, but now we use
> a trie structure there as well, and that uses full long word sized
> keys and the generic raidx-tree code.
>
> Using hash tables is really foolish for potentially large data sets.
>

However, I don't agree with you at every aspect.

Radix tree may cost lots of memory than a rbtree, avl tree or hash
table. Here is a case: turning to rbtree from radix tree.
http://git.kernel.org/?p=linux/kernel/git/davem/net-next-2.6.git;a=commit;h=8549164143a5431f9d9ea846acaa35a862410d9c

Since the keys of inetpeer rely on the access pattern, a attacker may
do a OOM DoS attack using sparse keys. We can't simply limit the
number of inetpeers to limit the memory cost of this subsystem. We
have to count the memory used for the inner branches of a radix tree.
Nevertheless, a attacker may also make this OS inefficiency by reduce
the max number of inetpeers.

Hash table + jhash have been proven a safe and efficient data
structure for large data sets(conntrack and ipvs), although the size
of the hash table may have to be adjusted by an administrator.

-- 
Regards,
Changli Gao(xiaosuo@...il.com)
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html