| 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 16:59:37 -0700
From: "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To: tridge@...ba.org
Cc: Pavel Machek <pavel@....cz>, 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 03:14:13PM -0700, Paul E. McKenney wrote:
> On Thu, Jul 09, 2009 at 07:42:27AM +1000, tridge@...ba.org wrote:
> > Hi Paul,
> >
> > These probabilities are way off. They assume that whatever interaction
> > happens in XP has infinite memory. The testing I've done indicates
> > that the memory for this interaction is very small (maybe 3 or 4? it's
> > hard to know precisely).
>
> Good to know! I will rework assuming that the memory is 4, let me
> know if you learn more.
>
> > I've also confirmed this with lots of testing. If the probability was
> > 39% for any directory size then I would have found it.
>
> This new information will likely reduce the predicted probability of
> bluescreen by several orders of magnitude for large directories. Not
> that much effect for small directories, but not a real issue given
> how low the probabilities are to begin with.
>
> > In all my testing I did not once produce a XP crash with the full
> > patch. To produce the XP crash I needed to have a reduced version of
> > the patch with less randomness.
>
> Well, let's see if I can produce a reasonably realistic model. :-)
> (I knew I should have gotten more sleep last night!!!)
This model assumes a finite memory, so that at least two files out of
a group of "l" recently opened files have to collide to result in a
bluescreen. I don't trust it yet, but thought I should give people a
chance to poke holes in it.
Thanx, Paul
------------------------------------------------------------------------
Results
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 9.15401625433259b-5 (1 in 11,000)
16384 4.576973184985319b-5 (1 in 22,000)
8192 2.288233388567135b-5 (1 in 44,000)
4096 1.143843845796893b-5 (1 in 87,000)
2048 5.716441632059139b-6 (1 in 170,000)
1024 2.855430941007629b-6 (1 in 350,000)
512 1.424922525947476b-6 (1 in 700,000)
256 7.096675510325187b-7 (1 in 1,400,000)
128 3.520398717286601b-7 (1 in 2,800,000)
64 1.732259841151157b-7 (1 in 5,800,000)
32 8.381902831793723b-8 (1 in 12,000,000)
16 3.911554742174612b-8 (1 in 26,000,000)
8 1.676380622425006b-8 (1 in 60,000,000)
4 5.587935438151892b-9 (1 in 179,000,000)
2 9.313225746154785b-10 (1 in 1,000,000,000)
1 0.0b0
This is for 2^32 random values per entry and a WinXP "memory" of four
entries.
------------------------------------------------------------------------
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. WinXP seems to have a limited
memory for recently opened files, and we assume that once this
memory is full, opening a new file causes one of the recently
opened files to be forgotten. The size of its memory appears
to be in the range of 3-4 based on Tridge's testing, so we
will assume the worst case (4) and parameterize with l=4.
o As noted earlier, the probability the infamous Birthday Paradox
is given by:
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. This is not
the probability of no bluescreen, but we will use this result
to calculate this probability while initially filling WinXP's
memory. I again use maxima, and again use the optimized form
based on the binomial function:
b(n,m):=binomial(n,m)*m!/n^m;
o See the attached .eps...
o The probability of no bluescreen while opening the first "l"
files is given by b(n,l), just as before.
o Given no bluescreen while opening the first "l" files, the
probability of no bluescreen while opening the "l+1"st file
is the probability of missing the "l-1" files that remain
after ejecting one of them to make room is "(n-l+1)/n".
The cumulative probability of no bluescreen is thus:
P(n,m,l) = b(n,l)*(n-l+1)/n
o We have the same situation when opening the "l+2"nd file,
the probability of no bluescreen is again "(n-l+1)/n".
o This situation will repeat "m-l" times, so that we have:
P(n,m,l) = b(n,l)*((n-l+1)/n)^(m-l)
In maxima-speak:
b(n,m):=binomial(n,m)*m!/n^m;
nbs(n,m,l):=b(n,l)*((n-l+1)/n)^(m-l);
The probability of bluescreening when faced with 32767 files
in a directory, 32^6 possible random values, and the capacity
to remember four files is then:
1-nbs(32^6,32767,4);
For floating-point results instead of a massive fraction:
bfloat(1-nbs(32^6,32767,4));
See below for the actual maxima output, typos and all.
------------------------------------------------------------------------
maxima
paulmck@...lmck-laptop:~$ 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) nbs(n,m,l):=b(n,l)*((n-l+1)/n)^(m-l);
n - l + 1 m - l
(%o2) nbs(n, m, l) := b(n, l) (---------)
n
(%i3) bfloat(1-nbs(32^6,32767,4));
(%o3) 9.15401625433259b-5
(%i4) bfloat(1-nbs(32^6,2^14,4));
(%o4) 4.576973184985319b-5
(%i5) bfloat(1-nbs(32^6,2^13,4));
(%o5) 2.288233388567135b-5
(%i6) bfloat(1-nbs(32^6,2^12,4));
(%o6) 1.143843845796893b-5
(%i7) bfloat(1-nbs(32^6,2^11,4));
(%o7) 5.716441632059139b-6
(%i8) bfloat(1-nbs(32^6,2^10,4));
(%o8) 2.855430941007629b-6
(%i9) bfloat(1-nbs(32^6,2^9,4));
(%o9) 1.424922525947476b-6
(%i10) bfloat(1-nbs(32^6,2^8,4));
(%o10) 7.096675510325187b-7
(%i11) bfloat(1-nbs(32^6,2^7,4));
(%o11) 3.520398717286601b-7
(%i12) bfloat(1-nbs(32^6,2^6,4));
(%o12) 1.732259841151157b-7
(%i13) bfloat(1-nbs(32^6,2^5,4));
(%o13) 8.381902831793723b-8
(%i14) bfloat(1-nbs(32^6,2^4,4));
(%o14) 3.911554742174612b-8
(%i15) bfloat(1-nbs(32^6,2^3,4));
(%o15) 1.676380622425006b-8
(%i16) bfloat(1-nbs(32^6,2^2,4));
(%o16) 5.587935438151892b-9
(%i17) bfloat(1-nbs(32^6,2^1,4));
(%o17) - 1.734723480823569b-18
(%i18) bfloat(1-b(32^6,2));
(%o18) 9.313225746154785b-10
(%i19) bfloat(1-b(32^6,1));
(%o19) 0.0b0
Download attachment "WinXPmodel.eps" of type "application/postscript" (8454 bytes)
Powered by blists - more mailing lists