| 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
| ||
|
Date: Wed, 8 Jul 2009 07:25:20 -0700
From: "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To: Pavel Machek <pavel@....cz>
Cc: tridge@...ba.org, Rusty Russell <rusty@...tcorp.com.au>,
OGAWA Hirofumi <hirofumi@...l.parknet.co.jp>,
john.lanza@...ux.com, linux-kernel@...r.kernel.org,
linux-fsdevel@...r.kernel.org,
Dave Kleikamp <shaggy@...ux.vnet.ibm.com>,
Steve French <sfrench@...ibm.com>,
Mingming Cao <cmm@...ibm.com>
Subject: Re: [PATCH] Added CONFIG_VFAT_FS_DUALNAMES option
On Wed, Jul 08, 2009 at 11:21:33AM +0200, Pavel Machek wrote:
> On Fri 2009-07-03 09:59:35, tridge@...ba.org wrote:
> > Hi Pavel,
> >
> > > That's why we have ethernet checksums.
> >
> > which of course just changes the number of bits. The argument remains
> > the same.
>
> Ok, so what is your estimate of XP crash probability?
Assuming the worst case where the user opens each file in the directory
of interest, the probability depends on the number of long-named files
in the given directory as follows (derivation at EOM):
Files Probability Odds
----- -------------------- -------
32767 3.934446601778345b-1 (39.3%)
16384 1.174969255061134b-1 (11.7%)
8192 3.076314519945223b-2 ( 3.1%)
4096 7.780179085651447b-3 ( 0.8%)
2048 1.950268317016874b-3 ( 0.2%)
1024 4.87685610530225b-4 (1 in 2,000)
512 1.218244920604881b-4 (1 in 8,000)
256 3.039790922077076b-5 (1 in 30,000)
128 7.569761535306629b-6 (1 in 100,000)
64 1.877544584847826b-6 (1 in 500,000)
32 4.61935894834079b-7 (1 in 2,000,000)
16 1.117587032466174b-7 (1 in 9,000,000)
8 2.607703180994292b-8 (1 in 38,000,000)
4 5.587935438151892b-9 (1 in 180,000,000)
2 9.313225746154785b-10 (1 in 1,000,000,000)
1 0.0b0
The number of files that people keep in a given directory will vary,
but in my admittedly limited experience, most people tend towards the
low end of this range. What number of files per directory do you see
on embedded-device memory sticks?
Furthermore, this assumes that the user actually opens each and every file
in the directory. If the user keeps (say) 1024 files in the directory,
but only opens two of them on any given memory-stick insertion, then
the odds are one in a billion rather than one in two thousand.
[Tridge -- isn't this only for subdirectories? Or can collisions in
the root directory also result in WinXP bluescreens?]
> > > It already _was_ perfect before you started patching it.
> >
> > wow, I really didn't expect the objection to my patch to be that VFAT
> > is perfect!
>
> But ... it was, and there is still possibility of just using position
> in directory to avoid collisions completely.
Almost. The imperfection comes from the fact that storage media are not
totally reliable, so that given enough uses of large enough numbers of
memory sticks, there will eventually be a WinXP bluescreen. Please note
that people really have reported this WinXP bug.
Thanx, Paul
------------------------------------------------------------------------
Derivation:
o The patch uses 6 random bytes, with 6 bits each, for
32^6 = 1,073,741,824 possible combinations. (Based on code
in vfat_build_dummy_83_buffer() in the patch Tridge posted on
June 27th.)
o There are a maximum of 32,767 entries in a VFAT directory.
o In the worst case, the user application will open each and
every file in the directory. I don't have any information on
whether WinXP has a limited memory for recently open files.
I therefore assume the worst case, namely that WinXP remembers
every file that it has opened.
o As noted in this thread, the probability of bluescreen is
given by the infamous Birthday Paradox:
P(n, m) = (n-1)! / ((n-m)! * n^(m-1))
Here "n" is the number of possible birthdays (1,073,741,824 in
this case) and "m" is the number of people (32,767 in this case).
P(n, m) is the probability of -no- common birthday, so the
probability of WinXP bluescreen is 1-P(n,m).
Because I don't want to worry about round-off error, I use the
arbitrary-precision arithmetic in the "maxima" symbolic-math
package, which is related to the fabled Macsyma project. However,
computing the factorials without cancellation takes too long,
so we transform the factorials into the binomial function, which
has a highly optimized maxima implementation. The equivalent
but more efficient representation is as follows:
b(n,m):=binomial(n,m)*m!/n^m;
Then 1-b(32^6,32767) gives the exact probability of bluescreen
on a maximal-sized directory, which is the ratio of a pair of
extremely large integers. More usefully, bfloat(1-b(32^6,32767))
gives an approximation in scientific notation. (Don't forget
the trailing semicolon that maxima requires.)
Computing bfloat(1-b(32^6,32767)) takes about 70 seconds on my
2GHz x86 laptop.
See below for the actual maxima output, typos and all.
------------------------------------------------------------------------
maxima
Maxima 5.12.0 http://maxima.sourceforge.net
Using Lisp GNU Common Lisp (GCL) GCL 2.6.7 (aka GCL)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
This is a development version of Maxima. The function bug_report()
provides bug reporting information.
(%i1) b(n,m):=binomial(n,m)*m!/n^m;
binomial(n, m) m!
(%o1) b(n, m) := -----------------
m
n
(%i2) bfloat(1-b(32^6,32767));
(%o2) 3.934446601778345b-1
(%i3) bfloat(1-b(32^6,2^14));
(%o3) 1.174969255061134b-1
(%i4) bfloat(1-b(32^6,2^13));
(%o4) 3.076314519945223b-2
(%i5) bfloat(1-b(32^6,2^12));
(%o5) 7.780179085651447b-3
(%i6) bfloat(1-b(32^6,2^11));
(%o6) 1.950268317016874b-3
(%i7) bfloat(1-b(32^6,2^10));
(%o7) 4.87685610530225b-4
(%i8) bfloat(1-b(32^6,2^9));
(%o8) 1.218244920604881b-4
(%i9) bfloat(1-b(32^6,2^8));
(%o9) 3.039790922077076b-5
(%i10) bfloat(1-b(32^6,2^7));
(%o10) 7.569761535306629b-6
(%i11) bfloat(1-b(32^6,2^6));
(%o11) 1.877544584847826b-6
(%i12) bfloat(1-b(32^6,2^));
Incorrect syntax: Illegal use of delimiter )
bfloat(1-b(32^6,2^)
^
(%i12) bfloat(1-b(32^6,2^5));
(%o12) 4.61935894834079b-7
(%i13) bfloat(1-b(32^6,2^4));
(%o13) 1.117587032466174b-7
(%i14) bfloat(1-b(32^6,2^3));
(%o14) 2.607703180994292b-8
(%i15) bfloat(1-b(32^6,2^2));
(%o15) 5.587935438151892b-9
(%i16) bfloat(1-b(32^6,2^1));
(%o16) 9.313225746154785b-10
(%i17) bfloat(1-b(32^6,2^0));
(%o17) 0.0b0
(%i18)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists