[RFT] Reed-Solomon

[RFT] Reed-Solomon

[Vladimir 'φ-coder/phcoder' Serbinenko]

[-- Attachment #1: Type: text/plain, Size: 268 bytes --]

Hello, all. I've just finished Reed-Solomon and pushedit to
branches/solomon. About 8 sectors (including MBR) aren't protected by
Reed-Solomon. Obviously it can be improved but that would be for post-1.99

-- 
Regards
Vladimir 'φ-coder/phcoder' Serbinenko



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 294 bytes --]

Re: [RFT] Reed-Solomon

[Phillip Susi]

On 9/25/2010 4:25 PM, Vladimir 'φ-coder/phcoder' Serbinenko wrote:
> Hello, all. I've just finished Reed-Solomon and pushedit to
> branches/solomon. About 8 sectors (including MBR) aren't protected by
> Reed-Solomon. Obviously it can be improved but that would be for post-1.99

So you are adding bit error detection and correction to the boot loader?
 You realize that the hard disk already does reed-solomon right?  So a
second layer of it doesn't seem to have much point.

Re: [RFT] Reed-Solomon

[Colin Watson]

On Mon, Sep 27, 2010 at 11:10:44AM -0400, Phillip Susi wrote:
> On 9/25/2010 4:25 PM, Vladimir 'φ-coder/phcoder' Serbinenko wrote:
> > Hello, all. I've just finished Reed-Solomon and pushedit to
> > branches/solomon. About 8 sectors (including MBR) aren't protected by
> > Reed-Solomon. Obviously it can be improved but that would be for post-1.99
> 
> So you are adding bit error detection and correction to the boot loader?
>  You realize that the hard disk already does reed-solomon right?  So a
> second layer of it doesn't seem to have much point.

You're missing context.

-- 
Colin Watson                                       [cjwatson@ubuntu.com]

Re: [RFT] Reed-Solomon

[Phillip Susi]

On 9/27/2010 12:12 PM, Colin Watson wrote:
>> So you are adding bit error detection and correction to the boot loader?
>>  You realize that the hard disk already does reed-solomon right?  So a
>> second layer of it doesn't seem to have much point.
> 
> You're missing context.

Apparently.  Fill me in?

Re: [RFT] Reed-Solomon

[Lennart Sorensen]

On Mon, Sep 27, 2010 at 05:10:23PM -0400, Phillip Susi wrote:
> On 9/27/2010 12:12 PM, Colin Watson wrote:
> >> So you are adding bit error detection and correction to the boot loader?
> >>  You realize that the hard disk already does reed-solomon right?  So a
> >> second layer of it doesn't seem to have much point.
> > 
> > You're missing context.
> 
> Apparently.  Fill me in?

FlexNet and similar like to write to track 0 sectors (outside partitioned
space) to store license info.  This clobbers part of grub potentially.
So to make grub more tolerant of such misbehaviour, the idea suggested
was to add error correction to grub so it can survive attacks on its code
(and even potential disk errors).

-- 
Len Sorensen

Re: [RFT] Reed-Solomon

[Phillip Susi]

On 9/27/2010 7:34 PM, Lennart Sorensen wrote:
> FlexNet and similar like to write to track 0 sectors (outside partitioned
> space) to store license info.  This clobbers part of grub potentially.
> So to make grub more tolerant of such misbehaviour, the idea suggested
> was to add error correction to grub so it can survive attacks on its code
> (and even potential disk errors).

Ahh, neat.  Two sectors of ECC can fix one that is completely destroyed?
 I was under the impression that you could only fix a few corrupted
bits, not an entire sector, but I suppose if you add enough ECC...  I
take it that someone has already made sure that the misbehaved software
only uses a single sector?

Re: [RFT] Reed-Solomon

[Colin Watson]

On Tue, Sep 28, 2010 at 11:13:40AM -0400, Phillip Susi wrote:
> On 9/27/2010 7:34 PM, Lennart Sorensen wrote:
> > FlexNet and similar like to write to track 0 sectors (outside partitioned
> > space) to store license info.  This clobbers part of grub potentially.
> > So to make grub more tolerant of such misbehaviour, the idea suggested
> > was to add error correction to grub so it can survive attacks on its code
> > (and even potential disk errors).
> 
> Ahh, neat.  Two sectors of ECC can fix one that is completely destroyed?
>  I was under the impression that you could only fix a few corrupted
> bits, not an entire sector, but I suppose if you add enough ECC...

http://en.wikipedia.org/wiki/Reed-Solomon_error_correction says that t
check symbols can correct up to floor(t/2) symbols.  (ISTR Vladimir said
he had a variant which did better than this, but I haven't looked yet.)

> I take it that someone has already made sure that the misbehaved
> software only uses a single sector?

All the examples I've seen so far are thus.  Of course if you have
multiple infections then you're doomed, but hopefully the probability of
multiple infections goes down fairly sharply ...

-- 
Colin Watson                                       [cjwatson@ubuntu.com]

Re: [RFT] Reed-Solomon

[Vladimir 'φ-coder/phcoder' Serbinenko]

[-- Attachment #1: Type: text/plain, Size: 1882 bytes --]

On 09/28/2010 05:26 PM, Colin Watson wrote:
> On Tue, Sep 28, 2010 at 11:13:40AM -0400, Phillip Susi wrote:
>   
>> On 9/27/2010 7:34 PM, Lennart Sorensen wrote:
>>     
>>> FlexNet and similar like to write to track 0 sectors (outside partitioned
>>> space) to store license info.  This clobbers part of grub potentially.
>>> So to make grub more tolerant of such misbehaviour, the idea suggested
>>> was to add error correction to grub so it can survive attacks on its code
>>> (and even potential disk errors).
>>>       
>> Ahh, neat.  Two sectors of ECC can fix one that is completely destroyed?
>>  I was under the impression that you could only fix a few corrupted
>> bits, not an entire sector, but I suppose if you add enough ECC...
>>     
> http://en.wikipedia.org/wiki/Reed-Solomon_error_correction says that t
> check symbols can correct up to floor(t/2) symbols.  (ISTR Vladimir said
> he had a variant which did better than this, but I haven't looked yet.)
>
>   
You need one symbol to figure out an error location and one to find the
correct value. Since I've chosen to do Reed-Solomon over GF(2^8) our
symbols are bytes. Under the supposition that corruption happens in one
sector you need only few bytes to figure which sector is corrupted and
then 512 bytes to fix it. But I didn't implement this improvement
>> I take it that someone has already made sure that the misbehaved
>> software only uses a single sector?
>>     
> All the examples I've seen so far are thus.  Of course if you have
> multiple infections then you're doomed, but hopefully the probability of
> multiple infections goes down fairly sharply ...
>
>   
My branch uses every available sector for redundancy info. So if you
have 2*n sectors left in MBR gap you can survive n corrupted sectors.


-- 
Regards
Vladimir 'φ-coder/phcoder' Serbinenko



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 294 bytes --]

Re: [RFT] Reed-Solomon

[Phillip Susi]

On 9/28/2010 12:36 PM, Vladimir 'φ-coder/phcoder' Serbinenko wrote:
> My branch uses every available sector for redundancy info. So if you
> have 2*n sectors left in MBR gap you can survive n corrupted sectors.

You might want to place a reasonable limit on that.  With conventional
62 sector gaps this could be a good idea, but with everyone moving to 1
MB gaps these days, over 2000 sectors of ecc could be overkill ;)

Re: [RFT] Reed-Solomon

[Vladimir 'φ-coder/phcoder' Serbinenko]

[-- Attachment #1: Type: text/plain, Size: 628 bytes --]

On 09/28/2010 08:45 PM, Phillip Susi wrote:
> On 9/28/2010 12:36 PM, Vladimir 'φ-coder/phcoder' Serbinenko wrote:
>   
>> My branch uses every available sector for redundancy info. So if you
>> have 2*n sectors left in MBR gap you can survive n corrupted sectors.
>>     
> You might want to place a reasonable limit on that.  With conventional
> 62 sector gaps this could be a good idea, but with everyone moving to 1
> MB gaps these days, over 2000 sectors of ecc could be overkill ;)
>
>   
Yes, limit is that redumdance is never longer as the data.


-- 
Regards
Vladimir 'φ-coder/phcoder' Serbinenko



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 294 bytes --]

Re: [RFT] Reed-Solomon

[Manoel Rebelo Abraches]

You can see a explanation at
http://lists.gnu.org/archive/html/grub-devel/2010-09/msg00205.html


-- 
Best Regards,

Manoel Rebelo Abranches
Software engineer
IBM - Linux Technology Center - Brazil