Re: Speeding up Tree Verification

Michał Górny <[email protected]> Wed, 01 Jul 2020 14:38:50 +0200
Newsgroups	gmane.linux.gentoo.portage.devel
Organization	Gentoo
Message-ID	<[email protected]>
On Tue, 2020-06-30 at 16:51 -0500, Sid Spry wrote:
> On Tue, Jun 30, 2020, at 2:29 PM, Michał Górny wrote:
> > On Tue, 2020-06-30 at 12:50 -0500, Sid Spry wrote:
> > > On Tue, Jun 30, 2020, at 2:28 AM, Michał Górny wrote:
> > > > Dnia June 30, 2020 2:13:43 AM UTC, Sid Spry <[email protected]> napisał(a):
> > > > > Hello,
> > > > > 
> > > > > I have some runnable pseudocode outlining a faster tree verification
> > > > > algorithm.
> > > > > Before I create patches I'd like to see if there is any guidance on
> > > > > making the
> > > > > changes as unobtrusive as possible. If the radical change in algorithm
> > > > > is
> > > > > acceptable I can work on adding the changes.
> > > > > 
> > > > > Instead of composing any kind of structured data out of the portage
> > > > > tree my
> > > > > algorithm just lists all files and then optionally batches them out to
> > > > > threads.
> > > > > There is a noticeable speedup by eliding the tree traversal operations
> > > > > which
> > > > > can be seen when running the algorithm with a single thread and
> > > > > comparing it to
> > > > > the current algorithm in gemato (which should still be discussed
> > > > > here?).
> > > > 
> > > > Without reading the code: does your algorithm correctly detect extraneous files?
> > > > 
> > > 
> > > Yes and no.
> > > 
> > > I am not sure why this is necessary. If the file does not appear in a manifest it is
> > > ignored. It makes the most sense to me to put the burden of not including
> > > untracked files on the publisher. If the user puts an untracked file into the tree it
> > > will be ignored to no consequence; the authored files don't refer to it, after all.
> > 
> > This is necessary because a malicious third party can MITM you an rsync
> > tree with extraneous files (say, -r1 baselayout ebuild) that do horrible
> > things on your system.  If you don't reject files not in Manifest, you
> > open a huge security hole.
> > 
> 
> Ok, I will refer to https://www.gentoo.org/glep/glep-0074.html and implement the
> checks in detail, but will still need to spend some time looking for the best place
> to insert the code.
> 
> I think it best to address this from two fronts. On one hand rejecting extra files
> seems to have immediate benefit but the larger issue is portage exposing
> untracked potentially malicious files to the user.

I've pushed two branches with two exploits I could think of.  Please
test your tools against them.  In both cases, the directory should be
rejected without any ill effects.

https://github.com/mgorny/glep74-test-cases

> 
> Has anything like a verity loopback filesystem been explored? It might reduce
> duplication of work.

I don't understand what a 'verity loopback filesystem' is.  Could you elaborate?

-- 
Best regards,
Michał Górny
signature.asc (application/pgp-signature, 618 B)