diff mbox

[3.13,163/163] lzo: check for length overrun in variable length encoding.

Message ID 1412888588-26755-164-git-send-email-kamal@canonical.com
State New
Headers show

Commit Message

Kamal Mostafa Oct. 9, 2014, 9:03 p.m. UTC
3.13.11.9 -stable review patch.  If anyone has any objections, please let me know.

------------------

From: Willy Tarreau <w@1wt.eu>

commit 72cf90124e87d975d0b2114d930808c58b4c05e4 upstream.

This fix ensures that we never meet an integer overflow while adding
255 while parsing a variable length encoding. It works differently from
commit 206a81c ("lzo: properly check for overruns") because instead of
ensuring that we don't overrun the input, which is tricky to guarantee
due to many assumptions in the code, it simply checks that the cumulated
number of 255 read cannot overflow by bounding this number.

The MAX_255_COUNT is the maximum number of times we can add 255 to a base
count without overflowing an integer. The multiply will overflow when
multiplying 255 by more than MAXINT/255. The sum will overflow earlier
depending on the base count. Since the base count is taken from a u8
and a few bits, it is safe to assume that it will always be lower than
or equal to 2*255, thus we can always prevent any overflow by accepting
two less 255 steps.

This patch also reduces the CPU overhead and actually increases performance
by 1.1% compared to the initial code, while the previous fix costs 3.1%
(measured on x86_64).

The fix needs to be backported to all currently supported stable kernels.

Reported-by: Willem Pinckaers <willem@lekkertech.net>
Cc: "Don A. Bailey" <donb@securitymouse.com>
Signed-off-by: Willy Tarreau <w@1wt.eu>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Kamal Mostafa <kamal@canonical.com>
---
 lib/lzo/lzo1x_decompress_safe.c | 43 +++++++++++++++++++++++++++++++++++------
 1 file changed, 37 insertions(+), 6 deletions(-)

Comments

Willy Tarreau Oct. 10, 2014, 5:30 a.m. UTC | #1
Hi Kamal,

[ removed Don Bailey from the CC who's certainly not interested in this ]

On Thu, Oct 09, 2014 at 02:03:08PM -0700, Kamal Mostafa wrote:
> 3.13.11.9 -stable review patch.  If anyone has any objections, please let me know.
> 
> ------------------
> 
> From: Willy Tarreau <w@1wt.eu>
> 
> commit 72cf90124e87d975d0b2114d930808c58b4c05e4 upstream.

(...)

This one (and the accompanying revert) are still not present in more
recent stable kernels, so I find it surprizing that you're proposing
to integrate them now. If someone upgrades from 3.13.11.9 to 3.14.21
or 3.16.5, they'd expect to keep all fixes but will lose this one, so
this is a bit confusing. Is there any reason you're not tracking fixes
from more recent versions like Jiri, Li, Ben and I are doing ?

Thanks,
Willy
Kamal Mostafa Oct. 13, 2014, 5:31 p.m. UTC | #2
On Fri, 2014-10-10 at 07:30 +0200, Willy Tarreau wrote:
> Hi Kamal,
> 
> [ removed Don Bailey from the CC who's certainly not interested in this ]
> 
> On Thu, Oct 09, 2014 at 02:03:08PM -0700, Kamal Mostafa wrote:
> > 3.13.11.9 -stable review patch.  If anyone has any objections, please let me know.
> > 
> > ------------------
> > 
> > From: Willy Tarreau <w@1wt.eu>
> > 
> > commit 72cf90124e87d975d0b2114d930808c58b4c05e4 upstream.
> 
> (...)

Hi Willy-

Thanks very much for reviewing this.

> This one (and the accompanying revert) are still not present in more
> recent stable kernels, so I find it surprizing that you're proposing
> to integrate them now.

I can hold out those lzo fixes until the next 3.13-stable if you prefer.
But fwiw...

>  If someone upgrades from 3.13.11.9 to 3.14.21
> or 3.16.5, they'd expect to keep all fixes but will lose this one, so
> this is a bit confusing.

I think those sorts of scheduling mismatches and discrepancies between
stable versions are pretty common.  Examples:  The top 11 commits in
v3.12.30 have not yet been applied[0] to any of the newer stable
branches;  Many of the commits in v3.10.57 have not yet been applied[1]
to linux-3.12.y but have been released in other newer stables.

>  Is there any reason you're not tracking fixes
> from more recent versions like Jiri, Li, Ben and I are doing ?

We (the Canonical stable maintainers) have always tracked the "cc:
stable" fixes directly from mainline, not from the more-recent-version
branches.  Given the examples above, it seems that the kernel.org
maintainers are doing that too, yes?

 -Kamal

[0] linux-3.12.y  1d08848..99ed1bd  (part of the big mm patch set)
[1] linux-3.10.y  07d209b..7dd3111  (various "cc: stable" patches)
Willy Tarreau Oct. 13, 2014, 6:48 p.m. UTC | #3
Hi Kamal,

On Mon, Oct 13, 2014 at 10:31:03AM -0700, Kamal Mostafa wrote:
> > This one (and the accompanying revert) are still not present in more
> > recent stable kernels, so I find it surprizing that you're proposing
> > to integrate them now.
> 
> I can hold out those lzo fixes until the next 3.13-stable if you prefer.

It would be better in my opinion.

> But fwiw...
> 
> >  If someone upgrades from 3.13.11.9 to 3.14.21
> > or 3.16.5, they'd expect to keep all fixes but will lose this one, so
> > this is a bit confusing.
> 
> I think those sorts of scheduling mismatches and discrepancies between
> stable versions are pretty common.

I don't think so. In my opinion when this happens it's mostly a mistake.

> Examples:  The top 11 commits in
> v3.12.30 have not yet been applied[0] to any of the newer stable
> branches;

I think this doesn't happen often and probably it's just a matter of
reporting it when it happens so that maintainers double-check on their
side.

> Many of the commits in v3.10.57 have not yet been applied[1]
> to linux-3.12.y but have been released in other newer stables.

In Jiri's defense, he's in the middle of two versions managed by Greg,
so when Greg sends a batch of 3.10+3.14 releases, there is a small
window where 3.12 can be lagging a bit. But I think that this is
different from having patches that are not in the most recent
versions because users are much less likely to upgrade from one of
Greg's maintained kernels to any of ours than the opposite.

> >  Is there any reason you're not tracking fixes
> > from more recent versions like Jiri, Li, Ben and I are doing ?
> 
> We (the Canonical stable maintainers) have always tracked the "cc:
> stable" fixes directly from mainline, not from the more-recent-version
> branches.  Given the examples above, it seems that the kernel.org
> maintainers are doing that too, yes?

Possible, I don't know for others though I know that Greg tends to
be picky about mistakes like this not to happen too often, so I
suspect there's a bit of care there. I'm personally in a special
situation considering that I'm on the tail so the amount of changes
to apply to certain patches to backport them suggests that I more
often pick them from 3.2 or 3.4 than mainline (except for the ones
that I receive directly).

I can't speak for Greg but I think that sometimes if you notice that
you're merging a patch which is missing in most recent -stable branches,
it would be nice to send a reminder about it, as it's certainly possible
that one slips through from time to time.
 
Thanks,
Willy
Greg Kroah-Hartman Oct. 14, 2014, 1:52 a.m. UTC | #4
On Mon, Oct 13, 2014 at 10:31:03AM -0700, Kamal Mostafa wrote:
> On Fri, 2014-10-10 at 07:30 +0200, Willy Tarreau wrote:
> > Hi Kamal,
> > 
> > [ removed Don Bailey from the CC who's certainly not interested in this ]
> > 
> > On Thu, Oct 09, 2014 at 02:03:08PM -0700, Kamal Mostafa wrote:
> > > 3.13.11.9 -stable review patch.  If anyone has any objections, please let me know.
> > > 
> > > ------------------
> > > 
> > > From: Willy Tarreau <w@1wt.eu>
> > > 
> > > commit 72cf90124e87d975d0b2114d930808c58b4c05e4 upstream.
> > 
> > (...)
> 
> Hi Willy-
> 
> Thanks very much for reviewing this.
> 
> > This one (and the accompanying revert) are still not present in more
> > recent stable kernels, so I find it surprizing that you're proposing
> > to integrate them now.
> 
> I can hold out those lzo fixes until the next 3.13-stable if you prefer.

Please do so.

> But fwiw...
> 
> >  If someone upgrades from 3.13.11.9 to 3.14.21
> > or 3.16.5, they'd expect to keep all fixes but will lose this one, so
> > this is a bit confusing.
> 
> I think those sorts of scheduling mismatches and discrepancies between
> stable versions are pretty common.  Examples:  The top 11 commits in
> v3.12.30 have not yet been applied[0] to any of the newer stable
> branches;

Those -mm patches from Mel are "special", I'm taking it slow in merging
them, doing lots of local testing and code review, and not all of them
even are relevant for 3.14, so don't take the acceptance /
non-acceptance of them as any kind of "proof" of anything at all.

> Many of the commits in v3.10.57 have not yet been applied[1]
> to linux-3.12.y but have been released in other newer stables.

That's because I am ahead of Jiri, which will almost always happen due
to our different workflows and time available to spend on stable
kernels.

> >  Is there any reason you're not tracking fixes
> > from more recent versions like Jiri, Li, Ben and I are doing ?
> 
> We (the Canonical stable maintainers) have always tracked the "cc:
> stable" fixes directly from mainline, not from the more-recent-version
> branches.  Given the examples above, it seems that the kernel.org
> maintainers are doing that too, yes?

You have included patches in your release that are not in _any_ public
release on kernel.org yet.  Which is fine, you are allowed to do
whatever you want, but that goes against the existing rules of stable
patches that we have been following for well over the past year for when
it is acceptable to add a patch to a stable release.

Yet another reason I _strongly_ urge you to mark your kernels with some
type of "name" to help reduce the confusion of others that your kernels
might be somehow associated with kernel.org releases.

greg k-h
Luis Henriques Oct. 14, 2014, 8:58 a.m. UTC | #5
On Tue, Oct 14, 2014 at 03:52:33AM +0200, Greg Kroah-Hartman wrote:
> On Mon, Oct 13, 2014 at 10:31:03AM -0700, Kamal Mostafa wrote:
> > On Fri, 2014-10-10 at 07:30 +0200, Willy Tarreau wrote:
> > > Hi Kamal,
> > > 
> > > [ removed Don Bailey from the CC who's certainly not interested in this ]
> > > 
> > > On Thu, Oct 09, 2014 at 02:03:08PM -0700, Kamal Mostafa wrote:
> > > > 3.13.11.9 -stable review patch.  If anyone has any objections, please let me know.
> > > > 
> > > > ------------------
> > > > 
> > > > From: Willy Tarreau <w@1wt.eu>
> > > > 
> > > > commit 72cf90124e87d975d0b2114d930808c58b4c05e4 upstream.
> > > 
> > > (...)
> > 
> > Hi Willy-
> > 
> > Thanks very much for reviewing this.
> > 
> > > This one (and the accompanying revert) are still not present in more
> > > recent stable kernels, so I find it surprizing that you're proposing
> > > to integrate them now.
> > 
> > I can hold out those lzo fixes until the next 3.13-stable if you prefer.
> 
> Please do so.
> 
> > But fwiw...
> > 
> > >  If someone upgrades from 3.13.11.9 to 3.14.21
> > > or 3.16.5, they'd expect to keep all fixes but will lose this one, so
> > > this is a bit confusing.
> > 
> > I think those sorts of scheduling mismatches and discrepancies between
> > stable versions are pretty common.  Examples:  The top 11 commits in
> > v3.12.30 have not yet been applied[0] to any of the newer stable
> > branches;
> 
> Those -mm patches from Mel are "special", I'm taking it slow in merging
> them, doing lots of local testing and code review, and not all of them
> even are relevant for 3.14, so don't take the acceptance /
> non-acceptance of them as any kind of "proof" of anything at all.
> 
> > Many of the commits in v3.10.57 have not yet been applied[1]
> > to linux-3.12.y but have been released in other newer stables.
> 
> That's because I am ahead of Jiri, which will almost always happen due
> to our different workflows and time available to spend on stable
> kernels.
> 
> > >  Is there any reason you're not tracking fixes
> > > from more recent versions like Jiri, Li, Ben and I are doing ?
> > 
> > We (the Canonical stable maintainers) have always tracked the "cc:
> > stable" fixes directly from mainline, not from the more-recent-version
> > branches.  Given the examples above, it seems that the kernel.org
> > maintainers are doing that too, yes?
> 
> You have included patches in your release that are not in _any_ public
> release on kernel.org yet.  Which is fine, you are allowed to do
> whatever you want, but that goes against the existing rules of stable
> patches that we have been following for well over the past year for when
> it is acceptable to add a patch to a stable release.
> 

Could you please provide us with examples of commits in one of our
extended stable trees that is not on any other public release at
kernel.org?  We really try hard to follow the process defined for the
official stable kernels, so if this has happen in the past it was
definitely a mistake from our side, and we would love to get your
feedback during the review cycles.

My understanding is that Kamal queued this specific patch because its
related with a security issue (CVE-2014-4608): the original fix is
being reverted upstream and he is queuing this revert and the
alternative fix.  Anyway, since Willy objected, its likely Kamal will
postpone including these patches in the 3.13 kernel.

Cheers,
--
Luís

> Yet another reason I _strongly_ urge you to mark your kernels with some
> type of "name" to help reduce the confusion of others that your kernels
> might be somehow associated with kernel.org releases.
> 
> greg k-h
> 
> -- 
> kernel-team mailing list
> kernel-team@lists.ubuntu.com
> https://lists.ubuntu.com/mailman/listinfo/kernel-team
Jiri Slaby Oct. 16, 2014, 8:10 a.m. UTC | #6
On 10/14/2014, 10:58 AM, Luis Henriques wrote:
> Could you please provide us with examples of commits in one of our
> extended stable trees that is not on any other public release at
> kernel.org?

Hi, from 3.12.y, for example:
commit 48e8cad86bb1241c08bdaa80db022c25068ff8e0
Author: Jiri Slaby <jslaby@suse.cz>
Date:   Mon Jul 14 15:20:17 2014 +0200

    Revert "aio: fix kernel memory disclosure in io_getevents()
introduced in v3.10"

    This reverts commit 0e2e24e5dc6eb6f0698e9dc97e652f132b885624, which
    was applied twice mistakenly. The first one is
    bee3f7b8188d4b2a5dfaeb2eb4a68d99f67daecf.


Or any other patch without the "commit upstream" line. This may also
happen where there is no way of backporting a fix to the stable tree due
to later changes. Instead, a simple fix is applied, but it has no
connection to the original commit but the reference.

thanks,
Luis Henriques Oct. 16, 2014, 10:50 a.m. UTC | #7
On Thu, Oct 16, 2014 at 10:10:30AM +0200, Jiri Slaby wrote:
> On 10/14/2014, 10:58 AM, Luis Henriques wrote:
> > Could you please provide us with examples of commits in one of our
> > extended stable trees that is not on any other public release at
> > kernel.org?
> 
> Hi, from 3.12.y, for example:
> commit 48e8cad86bb1241c08bdaa80db022c25068ff8e0
> Author: Jiri Slaby <jslaby@suse.cz>
> Date:   Mon Jul 14 15:20:17 2014 +0200
> 
>     Revert "aio: fix kernel memory disclosure in io_getevents()
> introduced in v3.10"
> 
>     This reverts commit 0e2e24e5dc6eb6f0698e9dc97e652f132b885624, which
>     was applied twice mistakenly. The first one is
>     bee3f7b8188d4b2a5dfaeb2eb4a68d99f67daecf.
> 
> 
> Or any other patch without the "commit upstream" line. This may also
> happen where there is no way of backporting a fix to the stable tree due
> to later changes. Instead, a simple fix is applied, but it has no
> connection to the original commit but the reference.
> 

Thank you for your reply Jiri, but I believe you're referring to
commits that are in stable kernels and that are not on Linus tree.  I
do understand that these are required occasionally for the reasons you
stated above, and they are usually provided by subsystem maintainers.

However, the initial discussion was about commits that are not in a
public release (e.g. a Linus rc kernel) at kernel.org.

Cheers,
--
Luís
Greg Kroah-Hartman Oct. 16, 2014, 2:22 p.m. UTC | #8
On Tue, Oct 14, 2014 at 10:58:41AM +0200, Luis Henriques wrote:
> On Tue, Oct 14, 2014 at 03:52:33AM +0200, Greg Kroah-Hartman wrote:
> > On Mon, Oct 13, 2014 at 10:31:03AM -0700, Kamal Mostafa wrote:
> > > On Fri, 2014-10-10 at 07:30 +0200, Willy Tarreau wrote:
> > > > Hi Kamal,
> > > > 
> > > > [ removed Don Bailey from the CC who's certainly not interested in this ]
> > > > 
> > > > On Thu, Oct 09, 2014 at 02:03:08PM -0700, Kamal Mostafa wrote:
> > > > > 3.13.11.9 -stable review patch.  If anyone has any objections, please let me know.
> > > > > 
> > > > > ------------------
> > > > > 
> > > > > From: Willy Tarreau <w@1wt.eu>
> > > > > 
> > > > > commit 72cf90124e87d975d0b2114d930808c58b4c05e4 upstream.
> > > > 
> > > > (...)
> > > 
> > > Hi Willy-
> > > 
> > > Thanks very much for reviewing this.
> > > 
> > > > This one (and the accompanying revert) are still not present in more
> > > > recent stable kernels, so I find it surprizing that you're proposing
> > > > to integrate them now.
> > > 
> > > I can hold out those lzo fixes until the next 3.13-stable if you prefer.
> > 
> > Please do so.
> > 
> > > But fwiw...
> > > 
> > > >  If someone upgrades from 3.13.11.9 to 3.14.21
> > > > or 3.16.5, they'd expect to keep all fixes but will lose this one, so
> > > > this is a bit confusing.
> > > 
> > > I think those sorts of scheduling mismatches and discrepancies between
> > > stable versions are pretty common.  Examples:  The top 11 commits in
> > > v3.12.30 have not yet been applied[0] to any of the newer stable
> > > branches;
> > 
> > Those -mm patches from Mel are "special", I'm taking it slow in merging
> > them, doing lots of local testing and code review, and not all of them
> > even are relevant for 3.14, so don't take the acceptance /
> > non-acceptance of them as any kind of "proof" of anything at all.
> > 
> > > Many of the commits in v3.10.57 have not yet been applied[1]
> > > to linux-3.12.y but have been released in other newer stables.
> > 
> > That's because I am ahead of Jiri, which will almost always happen due
> > to our different workflows and time available to spend on stable
> > kernels.
> > 
> > > >  Is there any reason you're not tracking fixes
> > > > from more recent versions like Jiri, Li, Ben and I are doing ?
> > > 
> > > We (the Canonical stable maintainers) have always tracked the "cc:
> > > stable" fixes directly from mainline, not from the more-recent-version
> > > branches.  Given the examples above, it seems that the kernel.org
> > > maintainers are doing that too, yes?
> > 
> > You have included patches in your release that are not in _any_ public
> > release on kernel.org yet.  Which is fine, you are allowed to do
> > whatever you want, but that goes against the existing rules of stable
> > patches that we have been following for well over the past year for when
> > it is acceptable to add a patch to a stable release.
> > 
> 
> Could you please provide us with examples of commits in one of our
> extended stable trees that is not on any other public release at
> kernel.org?  We really try hard to follow the process defined for the
> official stable kernels, so if this has happen in the past it was
> definitely a mistake from our side, and we would love to get your
> feedback during the review cycles.

I don't really know, and honestly, don't care to spend the time and
energy to dig through to find this out.  The lzo ones jumped out at me
as I know the history behind them, and if you note, _I_ even didn't put
them in a stable kernel yet, as they have not shown up in a release from
Linus.

As the maintainer involved didn't ask you to go against the well-known
stable tree rules, that's a warning to others that perhaps something is
wrong here...

best of luck,

greg k-h
diff mbox

Patch

diff --git a/lib/lzo/lzo1x_decompress_safe.c b/lib/lzo/lzo1x_decompress_safe.c
index 569985d..a1c387f 100644
--- a/lib/lzo/lzo1x_decompress_safe.c
+++ b/lib/lzo/lzo1x_decompress_safe.c
@@ -25,6 +25,16 @@ 
 #define NEED_OP(x)      if (!HAVE_OP(x)) goto output_overrun
 #define TEST_LB(m_pos)  if ((m_pos) < out) goto lookbehind_overrun
 
+/* This MAX_255_COUNT is the maximum number of times we can add 255 to a base
+ * count without overflowing an integer. The multiply will overflow when
+ * multiplying 255 by more than MAXINT/255. The sum will overflow earlier
+ * depending on the base count. Since the base count is taken from a u8
+ * and a few bits, it is safe to assume that it will always be lower than
+ * or equal to 2*255, thus we can always prevent any overflow by accepting
+ * two less 255 steps. See Documentation/lzo.txt for more information.
+ */
+#define MAX_255_COUNT      ((((size_t)~0) / 255) - 2)
+
 int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
 			  unsigned char *out, size_t *out_len)
 {
@@ -55,12 +65,19 @@  int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
 		if (t < 16) {
 			if (likely(state == 0)) {
 				if (unlikely(t == 0)) {
+					size_t offset;
+					const unsigned char *ip_last = ip;
+
 					while (unlikely(*ip == 0)) {
-						t += 255;
 						ip++;
 						NEED_IP(1);
 					}
-					t += 15 + *ip++;
+					offset = ip - ip_last;
+					if (unlikely(offset > MAX_255_COUNT))
+						return LZO_E_ERROR;
+
+					offset = (offset << 8) - offset;
+					t += offset + 15 + *ip++;
 				}
 				t += 3;
 copy_literal_run:
@@ -116,12 +133,19 @@  copy_literal_run:
 		} else if (t >= 32) {
 			t = (t & 31) + (3 - 1);
 			if (unlikely(t == 2)) {
+				size_t offset;
+				const unsigned char *ip_last = ip;
+
 				while (unlikely(*ip == 0)) {
-					t += 255;
 					ip++;
 					NEED_IP(1);
 				}
-				t += 31 + *ip++;
+				offset = ip - ip_last;
+				if (unlikely(offset > MAX_255_COUNT))
+					return LZO_E_ERROR;
+
+				offset = (offset << 8) - offset;
+				t += offset + 31 + *ip++;
 				NEED_IP(2);
 			}
 			m_pos = op - 1;
@@ -134,12 +158,19 @@  copy_literal_run:
 			m_pos -= (t & 8) << 11;
 			t = (t & 7) + (3 - 1);
 			if (unlikely(t == 2)) {
+				size_t offset;
+				const unsigned char *ip_last = ip;
+
 				while (unlikely(*ip == 0)) {
-					t += 255;
 					ip++;
 					NEED_IP(1);
 				}
-				t += 7 + *ip++;
+				offset = ip - ip_last;
+				if (unlikely(offset > MAX_255_COUNT))
+					return LZO_E_ERROR;
+
+				offset = (offset << 8) - offset;
+				t += offset + 7 + *ip++;
 				NEED_IP(2);
 			}
 			next = get_unaligned_le16(ip);